IVN
0%

graph

Posted on Edited on In
Symbols count in article: 20k Reading time ≈ 18 mins.

图好题选编

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 记录被遍历过的节点
boolean[] visited;
// 记录从起点到当前节点的路径
boolean[] onPath;

/* 图遍历框架 */
void traverse(Graph graph, int s) {
    if (visited[s]) return;
    // 经过节点 s，标记为已遍历
    visited[s] = true;
    // 做选择：标记节点 s 在路径上
    onPath[s] = true;
    for (int neighbor : graph.neighbors(s)) {
        traverse(graph, neighbor);
    }
    // 撤销选择：节点 s 离开路径
    onPath[s] = false;
}

797. All Paths From Source to Target

directed acyclic graph (DAG) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class LeetCode797 {
    List<List<Integer>> res;
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        res=new ArrayList<>();
        dfs(graph,0,new LinkedList<>()); //题目要求找从0到n-1的所有路径，只需遍历从vertex 0出发的路径即可
        return res;
    }

    void dfs(int[][] graph, int start, LinkedList<Integer> path){
        path.add(start);
        int n= graph.length;
        if(start==n-1){//一旦到达了n-1，便可更新res并返回
            res.add(new ArrayList<>(path));
            path.removeLast();
            return;
        }
        for (int i : graph[start]) {
            dfs(graph,i,path);
        }
        path.removeLast();
    }
}

207. Course Schedule

环检测算法

看到依赖问题，首先想到的就是把问题转化成「有向图」这种数据结构，只要图中存在环，那就说明存在循环依赖。

只要会遍历，就可以判断图中是否存在环了

法一：DFS

借助 onPath 数组判断是否存在环

遍历所有节点；若某一路径上出现重复节点，则存在环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class LeetCode207 {

    List<Integer>[] graph;
    boolean isCycle;
    boolean[] visited;
    boolean[] onPath;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        graph=buildGraph(numCourses,prerequisites);
        visited=new boolean[graph.length];
        onPath=new boolean[graph.length];
        for (int i = 0; i < graph.length; i++) { //需要遍历每一条路径，才能确定不存在环; 因此需要从每个顶点出发
            dfs(i);
        }
        return !isCycle;
    }

    List<Integer>[] buildGraph(int num, int[][] pres){
        List<Integer>[] graph=new List[num];
        for (int i = 0; i < graph.length; i++) {
            graph[i]=new LinkedList<>();
        }
        for (int[] pre : pres) {
            int from=pre[1];
            int to=pre[0];
            graph[from].add(to);
        }
        return graph;
    }

    void dfs(int start){
        //注意：onPath和visited的判断不能调换次序
        //否则会漏掉环！！！
        if(onPath[start]){//当前路径上第二次遇到该vertex
            isCycle=true;
        }
        if(visited[start] || isCycle){//已经遍历过的顶点无需再次遍历
            return;
        }
        visited[start]=true;
        onPath[start]=true;
        for (Integer i : graph[start]) {
            dfs(i);
        }
        onPath[start]=false;
    }
}

法二：BFS

借助 indegree 数组记录每个节点的「入度」

若某节点没有入度，则可以作为topological sort的起点，加入队列进行遍历

如果所有节点都被遍历，则不成环，否则成环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<Integer>[] graph=new List[numCourses];
    for (int i = 0; i < graph.length; i++) {
        graph[i]=new LinkedList<>();
    }
    int[] inDegree=new int[graph.length];
    for (int[] pre : prerequisites) {
        int to=pre[0];
        int from=pre[1];
        graph[from].add(to);
        inDegree[to]++;
    }
    int count=0;
    Deque<Integer> queue=new LinkedList<>();
    for (int i = 0; i < inDegree.length; i++) {
        if(inDegree[i]==0){
            queue.offer(i);
        }
    }
    while(!queue.isEmpty()){
        int pre=queue.poll();
        count++;
        for (int next : graph[pre]) {
            inDegree[next]--;
            if(inDegree[next]==0){
                queue.offer(next);
            }
        }
    }

    return count==numCourses ? true : false;
}

210. Course Schedule II

拓扑排序：

  1. Topological Sorting
  2. 直观地说就是，让你把一幅图「拉平」，而且这个「拉平」的图里面，所有箭头方向都是一致的
  3. 如果一幅图是「有向无环图」，那么一定可以进行拓扑排序。
  4. 将后序遍历的结果进行反转，就是拓扑排序的结果。

法一：DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public class LeetCode210 {
    List<Integer>[] graph;
    boolean[] visited;
    boolean[] onPath;
    boolean hasCycle;
    LinkedList<Integer> path;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        graph=build(numCourses,prerequisites);
        path=new LinkedList<>();
        visited=new boolean[numCourses];
        onPath=new boolean[numCourses];

        for (int i = 0; i < numCourses; i++) {
            dfs(i);
        }

        if(hasCycle){
            return new int[0];
        }else{
            Collections.reverse(path);
            int[] res=new int[path.size()];
            for (int i = 0; i < res.length; i++) {
                res[i]=path.get(i);
            }
            return res;
        }
    }

    List<Integer>[] build(int num, int[][] pres){
        LinkedList<Integer>[] graph=new LinkedList[num];
        for (int i = 0; i < num; i++) {
            graph[i]=new LinkedList<>();
        }
        for (int[] pre : pres) {
            int from=pre[1];
            int to=pre[0];
            graph[from].add(to);
        }
        return graph;
    }

    void dfs(int start){
        if(onPath[start]){
            hasCycle=true;
        }
        if(hasCycle || visited[start]){
            return;
        }
        visited[start]=true;
        onPath[start]=true;

        for (int i : graph[start]) {
            dfs(i);
        }

        //后序遍历插入
        path.add(start);
        onPath[start]=false;
    }
}

法二：BFS

同207的BFS算法，入度为0队列弹出节点的顺序即为拓扑排序结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public int[] findOrder(int numCourses, int[][] prerequisites) {
    List<Integer>[] graph=new List[numCourses];
    int[] inDegree=new int[numCourses];
    for (int i = 0; i < graph.length; i++) {
        graph[i]=new LinkedList<>();
    }
    for (int[] pre : prerequisites) {
        int to=pre[0];
        int from=pre[1];
        graph[from].add(to);
        inDegree[to]++;
    }
    int count=0;
    int[] res=new int[numCourses];
    Deque<Integer> queue=new LinkedList<>();
    for (int i = 0; i < inDegree.length; i++) {
        if(inDegree[i]==0){
            queue.offer(i);
        }
    }
    while(!queue.isEmpty()){
        int pre=queue.poll();
        res[count++]=pre;
        for (Integer next : graph[pre]) {
            inDegree[next]--;
            if(inDegree[next]==0){
                queue.offer(next);
            }
        }
    }
    if(count<numCourses){
        return new int[]{};
    }else{
        return res;
    }
}

743. Network Delay Time

Dijkstra

1
2
// 输入一幅图和一个起点 start，计算 start 到其他节点的最短距离
int[] dijkstra(int start, List<Integer>[] graph);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// 返回节点 from 到节点 to 之间的边的权重
int weight(int from, int to);

// 输入节点 s 返回 s 的相邻节点
List<Integer> adj(int s);

// 输入一幅图和一个起点 start，计算 start 到其他节点的最短距离
int[] dijkstra(int start, List<Integer>[] graph) {
    // 图中节点的个数
    int V = graph.length;
    // 记录最短路径的权重，你可以理解为 dp table
    // 定义：distTo[i] 的值就是节点 start 到达节点 i 的最短路径权重
    int[] distTo = new int[V];
    // 求最小值，所以 dp table 初始化为正无穷
    Arrays.fill(distTo, Integer.MAX_VALUE);
    // base case，start 到 start 的最短距离就是 0
    distTo[start] = 0;

    // 优先级队列，distFromStart 较小的排在前面
    Queue<State> pq = new PriorityQueue<>((a, b) -> {
        return a.distFromStart - b.distFromStart;
    });

    // 从起点 start 开始进行 BFS
    pq.offer(new State(start, 0));

    while (!pq.isEmpty()) {
        State curState = pq.poll();
        int curNodeID = curState.id;
        int curDistFromStart = curState.distFromStart;
        
        
        //若是求到某一点的最短路径，则增加return判断
        //PriorityQueue保证了第一次遇到end时，就是最短的距离
        if (curNodeID == end) {
            return curDistFromStart;
        }

        if (curDistFromStart > distTo[curNodeID]) {
            // 已经有一条更短的路径到达 curNode 节点了
            continue;
        }
        // 将 curNode 的相邻节点装入队列
        for (int nextNodeID : adj(curNodeID)) {
            // 看看从 curNode 达到 nextNode 的距离是否会更短
            int distToNextNode = distTo[curNodeID] + weight(curNodeID, nextNodeID);
            if (distTo[nextNodeID] > distToNextNode) {
                // 更新 dp table
                distTo[nextNodeID] = distToNextNode;
                // 将这个节点以及距离放入队列
                pq.offer(new State(nextNodeID, distToNextNode));
            }
        }
    }
    return distTo;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class State{
    int id;
    int dist;
    State(int id, int dist){
        this.id=id;
        this.dist=dist;
    }
}

public int networkDelayTime(int[][] times, int n, int k) {
    List<int[]>[] graph=new List[n+1];
    for (int i = 1; i <= n; i++) {
        graph[i]=new LinkedList<>();
    }

    for (int[] time : times) {
        int from=time[0];
        int to=time[1];
        int edge=time[2];
        graph[from].add(new int[]{to,edge});
    }

    int[] md=new int[n+1];
    Arrays.fill(md,Integer.MAX_VALUE);
    md[k]=0;

    PriorityQueue<State> pq=new PriorityQueue<>(new Comparator<State>() {
        @Override
        public int compare(State o1, State o2) {
            return o1.dist-o2.dist;
        }
    });
    pq.offer(new State(k,0));
    while(!pq.isEmpty()){
        State cur=pq.poll();
        if(md[cur.id]<cur.dist){
            continue;
        }

        for (int[] next : graph[cur.id]) {
            int to=next[0];
            int edge=next[1];
            if(cur.dist+edge<md[to]){
                md[to]=cur.dist+edge;
                pq.offer(new State(to,md[to]));
            }
        }
    }
    int max=Integer.MIN_VALUE;
    for (int i = 1; i <= n; i++) {
        max=Math.max(max,md[i]);
    }
    return max==Integer.MAX_VALUE ? -1 : max;
}

787. Cheapest Flights Within K Stops

相比最正统的dijkstra，注意：

  1. 只求到某一点的最短距离，可以提前return
  2. 考虑经过的节点数的限制，若不满足则continue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
    List<int[]>[] graph = new LinkedList[n];
    for (int i = 0; i < n; i++) {
        graph[i] = new LinkedList<>();
    }
    for (int[] edge : flights) {
        int from = edge[0];
        int to = edge[1];
        int price = edge[2];
        graph[from].add(new int[]{to, price});
    }

    // 启动 dijkstra 算法
    // 计算以 src 为起点在 k 次中转到达 dst 的最短路径
    K++;
    return dijkstra(graph, src, K, dst);
}

class State {
    // 图节点的 id
    int id;
    // 从 src 节点到当前节点的花费
    int costFromSrc;
    // 从 src 节点到当前节点经过的节点个数
    int nodeNumFromSrc;

    State(int id, int costFromSrc, int nodeNumFromSrc) {
        this.id = id;
        this.costFromSrc = costFromSrc;
        this.nodeNumFromSrc = nodeNumFromSrc;
    }
}

// 输入一个起点 src，计算从 src 到其他节点的最短距离
int dijkstra(List<int[]>[] graph, int src, int k, int dst) {
    // 定义：从起点 src 到达节点 i 的最短路径权重为 distTo[i]
    int[] distTo = new int[graph.length];
    // 定义：从起点 src 到达节点 i 至少要经过 nodeNumTo[i] 个节点
    int[] nodeNumTo = new int[graph.length];
    Arrays.fill(distTo, Integer.MAX_VALUE);
    Arrays.fill(nodeNumTo, Integer.MAX_VALUE);
    // base case
    distTo[src] = 0;
    nodeNumTo[src] = 0;

    // 优先级队列，costFromSrc 较小的排在前面
    Queue<State> pq = new PriorityQueue<>((a, b) -> {
        return a.costFromSrc - b.costFromSrc;
    });
    // 从起点 src 开始进行 BFS
    pq.offer(new State(src, 0, 0));

    while (!pq.isEmpty()) {
        State curState = pq.poll();
        int curNodeID = curState.id;
        int costFromSrc = curState.costFromSrc;
        int curNodeNumFromSrc = curState.nodeNumFromSrc;
        
        if (curNodeID == dst) {
            // 找到最短路径
            return costFromSrc;
        }
        if (curNodeNumFromSrc == k) {
            // 中转次数耗尽
            continue;
        }

        // 将 curNode 的相邻节点装入队列
        for (int[] neighbor : graph[curNodeID]) {
            int nextNodeID = neighbor[0];
            int costToNextNode = costFromSrc + neighbor[1];
            // 中转次数消耗 1
            int nextNodeNumFromSrc = curNodeNumFromSrc + 1;

            // 更新 dp table
            if (distTo[nextNodeID] > costToNextNode) {
                distTo[nextNodeID] = costToNextNode;
                nodeNumTo[nextNodeID] = nextNodeNumFromSrc;
            }
            // 剪枝，如果中转次数更多，花费还更大，那必然不会是最短路径
            if (costToNextNode > distTo[nextNodeID]
                && nextNodeNumFromSrc > nodeNumTo[nextNodeID]) {
                continue;
            }
            
            pq.offer(new State(nextNodeID, costToNextNode, nextNodeNumFromSrc));
        }
    }
    return -1;
}

277. Find the Celebrity

名人节点的出度为 0，入度为 n - 1。

图有两种存储形式，一种是邻接表，一种是邻接矩阵，邻接表的主要优势是节约存储空间；邻接矩阵的主要优势是可以迅速判断两个节点是否相邻。

虽然判断一个人「是名人」必须用一个 for 循环，但判断一个人「不是名人」就不用这么麻烦了。

因为「名人」的定义保证了「名人」的唯一性，所以我们可以利用排除法，先排除那些显然不是「名人」的人，从而避免 for 循环的嵌套，降低时间复杂度。

我们可以不断从候选人中选两个出来，然后排除掉一个，直到最后只剩下一个候选人，这时候再使用一个 for 循环判断这个候选人是否是货真价实的「名人」。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int findCelebrity(int n) {
    int candidate=0;
    for (int other = 0; other < n; other++) {
        if(knows(candidate,other) || !knows(other,candidate)){
            candidate=other;
        }
    }
    for (int other = 0; other < n; other++) {
        if(other==candidate){
            continue;
        }
        if(knows(candidate,other) || !knows(other,candidate)){
            return -1;
        }
    }
    return candidate;
}

997. Find the Town Judge

依葫芦画瓢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class LeetCode997 {
    public int findJudge(int n, int[][] trust) {
        boolean[][] matrix=new boolean[n+1][n+1];
        for (int[] arr : trust) {
            int a=arr[0];
            int b=arr[1];
            matrix[a][b]=true;
        }
        int candidate=1;
        for (int other = 2; other <= n; other++) {
            if(!matrix[other][candidate] || matrix[candidate][other]){
                candidate=other;
            }
        }
        for (int i = 1; i <= n; i++) {
            if(i!=candidate && !matrix[i][candidate] || matrix[candidate][i]){
                return -1;
            }
        }
        return candidate;
    }
}

818. Race Car

https://leetcode.com/problems/race-car/discuss/124326/Summary-of-the-BFS-and-DP-solutions-with-intuitive-explanation

BFS: slow!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public int racecar(int target) {
    Set<String> set=new HashSet<>();
    PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->(a[2]-b[2]));
    //curId, curSpeed, curStep
    pq.offer(new int[]{0,1,0});
    while(!pq.isEmpty()){
        int[] cur=pq.poll();
        int curId=cur[0];
        int curSpeed=cur[1];
        int curStep=cur[2];
        if(curId==target){
            return curStep;
        }
        int nextStep=curStep+1;
        //accelerate
        int nextId=curId+curSpeed;
        int nextSpeed=curSpeed*2;
        String s=nextId+","+nextSpeed;
        if(nextId>=0 && nextSpeed<=2*target &&!set.contains(s)){
            set.add(s);
            pq.offer(new int[]{nextId,nextSpeed,nextStep});
        }
        //reverse
        nextSpeed=curSpeed>0 ? -1 : 1;
        nextId=curId;
        s=nextId+","+nextSpeed;
        if(!set.contains(s)){
            set.add(s);
            pq.offer(new int[]{nextId,nextSpeed,nextStep});
        }

    }
    return -1;
}

Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public int racecar(int target) {
        int K = 33 - Integer.numberOfLeadingZeros(target - 1);
        int barrier = 1 << K;
        int[] dist = new int[2 * barrier + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[target] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<Node>(
            (a, b) -> a.steps - b.steps);
        pq.offer(new Node(0, target));

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int steps = node.steps, targ1 = node.target;
            if (dist[Math.floorMod(targ1, dist.length)] > steps) continue;

            for (int k = 0; k <= K; ++k) {
                int walk = (1 << k) - 1;
                int targ2 = walk - targ1;
                int steps2 = steps + k + (targ2 != 0 ? 1 : 0);

                if (Math.abs(targ2) <= barrier && steps2 < dist[Math.floorMod(targ2, dist.length)]) {
                    pq.offer(new Node(steps2, targ2));
                    dist[Math.floorMod(targ2, dist.length)] = steps2;
                }
            }
        }

        return dist[0];
    }
}

class Node {
    int steps, target;
    Node(int s, int t) {
        steps = s;
        target = t;
    }
}

1136. Parallel Courses

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public int minimumSemesters(int n, int[][] relations) {
    int[] ins=new int[n+1];
    List<Integer>[] graph=new List[n+1];
    for (int i = 1; i <= n; i++) {
        graph[i]=new ArrayList<>();
    }
    for (int[] relation : relations) {
        int from=relation[0];
        int to=relation[1];
        graph[from].add(to);
        ins[to]++;
    }
    Deque<Integer> q=new LinkedList<>();
    for (int i = 1; i <= n; i++) {
        if(ins[i]==0){
            q.offer(i);
        }
    }
    int res=0;
    int total=0;
    while(!q.isEmpty()){
        int size=q.size();
        while(size-->0){
            int cur=q.poll();
            total++;
            for (Integer next : graph[cur]) {
                ins[next]--;
                if(ins[next]==0){
                    q.offer(next);
                }
            }
        }
        res++;
    }
    return total==n ? res : -1;
}

1557. Minimum Number of Vertices to Reach All Nodes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
    int[] ins=new int[n];
    for (List<Integer> edge : edges) {
        int from=edge.get(0);
        int to=edge.get(1);
        ins[to]++;
    }
    List<Integer> res=new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if(ins[i]==0){
            res.add(i);
        }
    }
    return res;
}

1203. Sort Items by Groups Respecting Dependencies

双重bfs topological sort，好题！

反思：

  • 注意groupId可能不连贯
  • 遇到报错不要乱改，先从简单的debug办法入手，不要一上来就大改
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
    for (int i = 0; i < n; i++) {
        if(group[i]==-1){
            group[i]=m++;
        }
    }
    //sort items
    //sort groups
    int[] itemIns=new int[n];
    int[] groupIns=new int[m];
    List<List<Integer>> nextItems=new ArrayList<>();
    List<List<Integer>> nextGroups=new ArrayList<>();
    for (int i = 0; i < n; i++) {
        nextItems.add(new ArrayList<>());
    }
    for (int i = 0; i < m; i++) {
        nextGroups.add(new ArrayList<>());
    }
    for (int to = 0; to < n; to++) {
        for (Integer from : beforeItems.get(to)) {
            itemIns[to]++;
            nextItems.get(from).add(to);
            if(group[from]!=group[to]){
                groupIns[group[to]]++;
                nextGroups.get(group[from]).add(group[to]);
            }
        }
    }
    //if both no cycle, has valid answer
    List<Integer> sortedItems=topologicalSort(itemIns,nextItems);
    List<Integer> sortedGroups=topologicalSort(groupIns,nextGroups);
    if(sortedItems==null || sortedGroups==null){
        return new int[0];
    }
    List<Integer> res=new ArrayList<>();
    Map<Integer,List<Integer>> groupToItems=new HashMap<>();
    for (Integer item : sortedItems) {
        int groupId=group[item];
        groupToItems.putIfAbsent(groupId,new ArrayList<>());
        groupToItems.get(groupId).add(item);
    }
    for (Integer groupId : sortedGroups) {
        List<Integer> list=groupToItems.get(groupId);
        if(list!=null){
            for (Integer item : list) {
                res.add(item);
            }
        }
    }
    return res.stream().mapToInt(i->i).toArray();
}

private List<Integer> topologicalSort(int[] ins, List<List<Integer>> next){
    Deque<Integer> q=new LinkedList<>();
    int len=ins.length;
    for (int i = 0; i < len; i++) {
        if(ins[i]==0){
            q.offer(i);
        }
    }
    List<Integer> res=new ArrayList<>();
    while(!q.isEmpty()){
        int cur=q.poll();
        res.add(cur);
        for (Integer to : next.get(cur)) {
            ins[to]--;
            if(ins[to]==0){
                q.offer(to);
            }
        }
    }
    return res.size()==len ? res : null;
}

1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

法一： brute force bfs

很慢！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public int findTheCity(int n, int[][] edges, int distanceThreshold) {
    Map<Integer,Integer>[] neighbors=new Map[n];
    for (int i = 0; i < n; i++) {
        neighbors[i]=new HashMap<>();
    }
    for (int[] edge : edges) {
        int a=edge[0];
        int b=edge[1];
        neighbors[a].put(b,edge[2]);
        neighbors[b].put(a,edge[2]);
    }
    int res=0;
    int min=Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        int count=bfs(neighbors,n,i,distanceThreshold);
        if(count<=min){
            min=count;
            res=i;
        }
    }
    return res;
}

private int bfs(Map<Integer,Integer>[] neighbors, int n, int start, int threshold){
    PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->(a[1]-b[1]));
    //idx, dist
    boolean[] visited=new boolean[n];
    pq.offer(new int[]{start,0});
    int res=-1;
    while(!pq.isEmpty()){
        int[] cur=pq.poll();
        int idx=cur[0];
        int dist=cur[1];
        if(dist>threshold){
            break;
        }
        if(visited[idx]){
            continue;
        }
        visited[idx]=true;
        res++;
        for (Integer next : neighbors[idx].keySet()) {
            pq.offer(new int[]{next,dist+neighbors[idx].get(next)});
        }
    }
    return res;
}

法二：floyd

Time O(N^3)
Space O(N^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public int findTheCity(int n, int[][] edges, int distanceThreshold) {
    int[][] dist=new int[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(dist[i],10001);
    }
    for (int i = 0; i < n; i++) {
        dist[i][i]=0;
    }
    for (int[] edge : edges) {
        int a=edge[0];
        int b=edge[1];
        dist[a][b]=edge[2];
        dist[b][a]=edge[2];
    }
    //iterate all middle point k
    //iterate all pair (i,j),
    //try to benefit from this middle point
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j]=Math.min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }
    int res=0;
    int min=Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        int count=0;
        for (int j = 0; j < n; j++) {
            if(dist[i][j]<=distanceThreshold){
                count++;
            }
        }
        if(count<=min){
            min=count;
            res=i;
        }
    }
    return res;
}

1559. Detect Cycles in 2D Grid

注意：

  • 无需关注length，只需关注是否成环（visited)
  • dfs while keeping track of last visited node
  • 只需一个global visited即可，因为会判断值是否相同，不同的path并不会干扰
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
char[][] grid;
int row;
int col;
int[] dx=new int[]{0,0,1,-1};
int[] dy=new int[]{1,-1,0,0};
public boolean containsCycle(char[][] grid) {
    this.grid=grid;
    this.row=grid.length;
    this.col=grid[0].length;
    boolean found=false;
    boolean[][] visited=new boolean[row][col];
    a:for(int i=0; i<row; i++){
        for(int j=0; j<col; j++){
            if(!visited[i][j]){
                
                if(dfs(i,j,-1,-1,visited)){
                    found=true;
                    break a;
                }
            }
        }
    }
    return found;
}

private boolean dfs(int i, int j, int px, int py, boolean[][] visited){
    boolean res=false;
    visited[i][j]=true;
    for(int k=0; k<4; k++){
        int x=i+dx[k];
        int y=j+dy[k];
        //dfs, keep track of parent
        if(x>=0 && x<row && y>=0 && y<col && grid[x][y]==grid[i][j]){
            if(x!=px || y!=py){
                if(visited[x][y]){
                    return true;
                }
                res|=dfs(x,y,i,j,visited);
            }
        }
    }
    return res;
}