This is the 28th day of my participation in Gwen Challenge

Topic describes

This is bus route 815 on LeetCode. Difficulty is difficult.

Tag: “Graph theory BFS”, “bidirectional BFS”, “Graph theory search”

You are given an array routes representing a series of bus routes, where each routes[I] represents a bus route on which the i-th bus will cycle.

  • For example, routesroutes[0] = [1, 5, 7]It means that the 0th bus will always follow the sequence1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1...Such station routes are driven.

Now from source station (not on the bus at the beginning), you’re going to Target Station. Bus only.

Find the minimum number of buses. If it is impossible to reach the terminal station, return -1.

Example 1:

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6Copy the code

Example 2:

Input: routes = [[7, 12],,5,15 [4], [6], [15] 3,,12,13 [9]], the source = 15, target = 12 output: 1Copy the code

Tip:

  • 1 <= routes.length <= 500.
  • 1 <= routes[i].length <=
    1 0 5 10^5
  • All values in routes[I] are different
  • sum(routes[i].length) <=
    1 0 5 10^5
  • 0 <= routes[i][j] <
    1 0 6 10^6
  • 0 <= source, target <
    1 0 6 10^6

Fundamental analysis

For convenience, we make each bus stop a “station” from which one or more “routes” can be entered.

The question is what is the minimum route to be taken from the “starting station” to the “finishing station”.

Abstract each “route” as a point, when there is a “bus station” between different “routes”, add an undirected edge with edge weight of 111 to it.

One-way BFS

Since the shortest circuit is calculated on the graph with edge weight of 111, we can use BFS directly.

At the beginning, the “route” that can be entered by the “starting station” will be joined in the queue. Every time the “route” is taken out from the queue, check whether the route contains the “terminal station” :

  • Includes “terminal station” : return to the distance taken to enter the line
  • Not including “terminal stations” : traversing the stations included in the route will be entered by the route accessible from these stations

Some details: since it is the shortest route, it is meaningless to join the team repeatedly, so you need to check whether a new route has been in the team before.

Code:

class Solution {
    int s, t;
    int[][] rs;
    public int numBusesToDestination(int[][] _rs, int _s, int _t) {
        rs = _rs; s = _s; t = _t;
        if (s == t) return 0;
        int ans = bfs();
        return ans;
    }
    int bfs(a) {
        // Record the route available to a station
        Map<Integer, Set<Integer>> map = new HashMap<>();
        // The queue stores the route
        Deque<Integer> d = new ArrayDeque<>();
        // Hash table records the distance used to enter the route
        Map<Integer, Integer> m = new HashMap<>();
        int n = rs.length;
        for (int i = 0; i < n; i++) {
            for (int station : rs[i]) {
                // Enqueue routes accessible from the starting point
                if (station == s) {
                    d.addLast(i);
                    m.put(i, 1);
                }
                Set<Integer> set = map.getOrDefault(station, newHashSet<>()); set.add(i); map.put(station, set); }}while(! d.isEmpty()) {// Take the current route and the distance it took to enter the route
            int poll = d.pollFirst();
            int step = m.get(poll);

            // Walk through the stations included in the route
            for (int station : rs[poll]) {
                // If the destination is included, return the distance it took to enter the route
                if (station == t) return step;

                // The route initiated by the station of the line will join the queue
                Set<Integer> lines = map.get(station);
                if (lines == null) continue;
                for (int nr : lines) {
                    if(! m.containsKey(nr)) { m.put(nr, step +1); d.add(nr); }}}}return -1; }}Copy the code
  • Time complexity: Let the number of routes be
    n n     , the number of stations is
    m m     . The time complexity of drawing is
    O ( ∑ i = 0 n – 1 l e n ( r s [ i ] ) ) O(\sum_{i=0}^{n-1} len(rs[i]))     ;BFSIn part, each route will join the queue only once. In the worst case, each route will contain all stations, and the complexity is
    O ( n ∗ m ) O(n * m)     . The overall complexity is
    O ( n ∗ m + ∑ i = 0 n – 1 l e n ( r s [ i ] ) ) O(n * m + \sum_{i=0}^{n-1} len(rs[i]))     .
  • Space complexity: O(n∗m)O(n * m)O(n∗m)

Bidirectional BFS (and check if there is no solution for set preprocessing)

Another approach is to use bidirectional BFS.

First of all, the mapping method remains unchanged. Put the routes that can be entered by “starting point” and “end point” into queues in two directions respectively. If “public route is encountered” or “current route contains target location”, it means that the shortest path has been found.

In addition, we know that bidirectional BFS is inferior to one-way BFS in the absence of a solution. Therefore, we can use “parallel search set” for preprocessing to determine whether the “starting point” and “end point” are connected. If not, we can directly return −1-1−1 and call bidirectional BFS only when there is a solution.

Since the complexity of preprocessing using a “look up set” is similar to that of graph building, adding such preprocessing does not cross our upper limit of space-time complexity, so such preprocessing is beneficial. To some extent, the benefits of bidirectional BFS to reduce search space can be maximized.

Code:

class Solution {
    static int N = (int)1e6+10;
    static int[] p = new int[N];
    int find(int x) {
        if(p[x] ! = x) p[x] = find(p[x]);return p[x];
    }
    void union(int a, int b) {
        p[find(a)] = p[find(b)];
    }
    boolean query(int a, int b) {
        return find(a) == find(b);
    }
    int s, t;
    int[][] rs;
    public int numBusesToDestination(int[][] _rs, int _s, int _t) {
        rs = _rs; s = _s; t = _t;
        if (s == t) return 0;
        for (int i = 0; i < N; i++) p[i] = i;
        for (int[] r : rs) {
            for (int loc : r) {
                union(loc, r[0]); }}if(! query(s, t))return -1;
        int ans = bfs();
        return ans;
    }
    // Record the route available to a station
    Map<Integer, Set<Integer>> map = new HashMap<>();
    int bfs(a) {
        Deque<Integer> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
        Map<Integer, Integer> m1 = new HashMap<>(), m2 = new HashMap<>();
        
        int n = rs.length;
        for (int i = 0; i < n; i++) {
            for (int station : rs[i]) {
                // Add routes accessible from the starting point to the forward queue
                if (station == s) {
                    d1.addLast(i);
                    m1.put(i, 1);
                }
                // Add the route accessible from the destination to the reverse queue
                if (station == t) {
                    d2.addLast(i);
                    m2.put(i, 1);
                }
                Set<Integer> set = map.getOrDefault(station, newHashSet<>()); set.add(i); map.put(station, set); }}// If there is an intersection between the route initiated by the origin and the route initiated by the destination, return 1
        Set<Integer> s1 = map.get(s), s2 = map.get(t);
        Set<Integer> tot = new HashSet<>();
        tot.addAll(s1);
        tot.retainAll(s2);
        if(! tot.isEmpty())return 1;

        / / two-way BFS
        while(! d1.isEmpty() && ! d2.isEmpty()) {int t = -1;
            if (d1.size() <= d2.size()) {
                t = update(d1, m1, m2, t);
            } else {
                t = update(d2, m2, m1, s);
            }
            if(t ! = -1) return t;
        }

        return 0x3f3f3f3f; // never
    }
    int update(Deque<Integer> d, Map<Integer, Integer> cur, Map<Integer, Integer> other, int target) {
        // Take the current route and the distance it took to enter the route
        int poll = d.pollFirst();
        int step = cur.get(poll);

        // Walk through the stations included in the route
        for (int station : rs[poll]) {
            if (station == target) return step;
            // Walk through the routes that will be initiated by the stations of the line
            Set<Integer> lines = map.get(station);
            if (lines == null) continue;
            for (int nr : lines) {
                if (cur.containsKey(nr)) continue;
                if (other.containsKey(nr)) return step + other.get(nr);
                cur.put(nr, step + 1); d.add(nr); }}return -1; }}Copy the code
  • Time complexity: Let the number of routes be
    n n     , the number of stations is
    m m     . And the time complexity of searching set and building graph is
    O ( ∑ i = 0 n – 1 l e n ( r s [ i ] ) ) O(\sum_{i=0}^{n-1} len(rs[i]))     ;BFSFind the complexity of the shortest path
    O ( n ∗ m ) O(n * m)     . The overall complexity is
    O ( n ∗ m + ∑ i = 0 n – 1 l e n ( r s [ i ] ) ) O(n * m + \sum_{i=0}^{n-1} len(rs[i]))     .
  • Space complexity: O (n ∗ m + ∑ I = 0 n – 1 len (rs) [I]) O (n * m + \ sum_ {I = 0} ^ {}, n – 1 len (rs) [I]) O (n ∗ m + ∑ I = 0 n – 1 len (rs) [I])

The last

This is the No.815 of our “Brush through LeetCode” series. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.