【LeetCode】Day135-课程表 I&II

题目1、课程表

207. 课程表【中等】

题解

一道拓扑排序的题，翻译过来就是找图内有没有环，没有返回true，有返回false

DFS

课程表 II 比这道题多了求拓扑排序序列，题解写的更清晰点，题解可以直接看那道题，这道仅展示代码吧

class Solution {
    List<List<Integer>>edges=new ArrayList<>();
    int[] vis;
    boolean circle;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        vis=new int[numCourses];
        //建立邻接表
        for(int i=0;i<numCourses;i++)
            edges.add(new ArrayList<>());
        for(int[] info:prerequisites){
            edges.get(info[1]).add(info[0]);
        }
        //dfs
        for(int i=0;i<numCourses;i++){
            if(vis[i]==0)
                dfs(i);
        }
        return !circle;
    }
    public void dfs(int u){
        vis[u]=1;
        //遍历u的相邻节点,有环直接返回
        for(int v:edges.get(u)){
            if(vis[v]==0){
                dfs(v);
                if(circle)
                    return;
            }
            else if(vis[v]==1){
                circle=true;
                return;
            }
        }
        vis[u]=2;
        return;
    }
}
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

时间复杂度：$O(n+m)$，n为课程数，m为先修课程的要求数，图的bfs复杂度

空间复杂度：$O(n+m)$，邻接表的空间

BFS

class Solution {
    List<List<Integer>>edges=new ArrayList<>();
    int[] in;
    int count=0;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        in=new int[numCourses];
        for(int i=0;i<numCourses;i++)
            edges.add(new ArrayList<>());
        for(int[] info:prerequisites){
            edges.get(info[1]).add(info[0]);
            in[info[0]]++;
        }
        Queue<Integer>queue=new LinkedList<>();
        for(int i=0;i<numCourses;i++){
            if(in[i]==0)
                queue.offer(i);
        }
        while(!queue.isEmpty()){
            int node=queue.poll();
            count++;
            for(int v:edges.get(node)){
                in[v]--;
                if(in[v]==0)
                    queue.offer(v);
            }
        }
        if(count!=numCourses)
            return false;
        return true;
    }
}
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

时间复杂度：$O(n+m)$，n为课程数，m为先修课程的要求数，图的bfs复杂度

空间复杂度：$O(n+m)$，邻接表的空间

题目2、课程表 II

210. 课程表 II【中等】

题解

求解课程顺序，即求解图的拓扑排序

DFS

假设当前搜索到u，如果它的相邻节点都已经搜索完成，都在栈中，此时把u入栈，则u在栈顶，它的所有相邻节点的前面。
这样，对图进行一遍DFS，每个节点回溯时入栈。最终栈顶到栈底的序列就是一种拓扑排序。

1. 每个节点有三种状态
   未搜索：还没有搜索
   搜索中：搜索过，但还没有回溯到该节点
   已完成：搜索且回溯过
2. DFS算法流程：任取未搜索节点进行深度优先搜索遍历，将当前搜索节点u状态标记为 [搜索中]，遍历其相邻节点v
   v未搜索：搜索v，搜索完成回溯到u
   v搜索中：找到环！不存在拓扑排序
   v已完成：无需操作
   当u的所有相邻节点都为 已完成 时，u入栈，标记为 已完成

以输入[[1,0],[2,0],[3,1],[3,2]]为例，结构如下，

输出[0,2,1,3]

class Solution {
    List<List<Integer>>edges=new ArrayList<>();//邻接表
    int[] vis;//标记数组
    int[] res;//模拟栈
    int index;//栈下标
    boolean circle;//有无环
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        vis=new int[numCourses];
        res=new int[numCourses];
        index=numCourses-1;
        //初始化邻接表,每个节点开辟空间
        for(int i=0;i<numCourses;i++){
            edges.add(new ArrayList<>());
        }
        //存节点的邻接节点
        for(int[] info:prerequisites){
            edges.get(info[1]).add(info[0]);
        }
        //dfs
        for(int i=0;i<numCourses;i++){
            if(vis[i]==0){
                dfs(i);
            }
            if(circle)
                return new int[0];//有环返回
        }
        return res;
    }
    public void dfs(int u){
        vis[u]=1;//搜索中
        //遍历u的相邻节点
        for(int v:edges.get(u)){
            //v未搜索
            if(vis[v]==0){
                dfs(v);
                if(circle)
                    return;
            }
            //v搜索中
            else if(vis[v]==1){
                circle=true;
                return;
            }
        }
        vis[u]=2;//完成搜索
        res[index--]=u;//入栈
    }
}
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

时间复杂度：$O(n+m)$，n为课程数，m为先修课程的要求数，图的dfs复杂度

空间复杂度：$O(n+m)$，邻接表大小

BFS

核心思想就是：每次都找入度为0的节点，即已经没有任何先修课程了，可以开始学习

• BFS算法流程：使用队列进行BFS。开始时所有入度为0的节点入队，在BFS的每一步，取队首节点u
  u放入答案中。
  移除u的所有出边。如果某个相邻节点v入度变为0，将v入队。

class Solution {
    List<List<Integer>>edges=new ArrayList<>();//邻接表
    int[] in;//入度
    int[] res;//模拟队列
    int index;//队列下标
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        in=new int[numCourses];
        res=new int[numCourses];
        index=0;
        //初始化邻接表,每个节点开辟空间
        for(int i=0;i<numCourses;i++){
            edges.add(new ArrayList<>());
        }
        //存节点的邻接节点
        for(int[] info:prerequisites){
            edges.get(info[1]).add(info[0]);
            in[info[0]]++;
        }
        //入度为0节点入队
        Queue<Integer>queue=new LinkedList<>();
        for(int i=0;i<numCourses;i++){
            if(in[i]==0){
                queue.offer(i);
            }
        }
        //bfs
        while(!queue.isEmpty()){
            int node=queue.poll();
            res[index++]=node;
            //遍历相邻节点
            for(int out:edges.get(node)){
                in[out]--;
                if(in[out]==0)
                    queue.offer(out);
            }
        }
        //有环
        if(index!=numCourses)
            return new int[0];
        return res;
    }
}
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

时间复杂度：$O(n+m)$，n为课程数，m为先修课程的要求数，图的bfs复杂度

空间复杂度：$O(n+m)$，邻接表大小

p.s 我的第200道题啦！加油