【刷爆LeetCode】七月算法集训（30）拓扑排序

题目来源于知识星球—英雄算法联盟，七月算法集训专题

前言

跟随英雄算法联盟博主—英雄哪里出来，每天完成相应的算法练习，一个月后，必定会有所成长！
回顾五月集训的算法题！

一、207.课程表（中等）

1.题目描述

2.解题思路

纯拓扑排序模板。看题解写的，多多加深理解！
1

3.代码演示（C++）

class Solution 
{
    #define maxn 100010
    vector <int> edges[maxn];
    int deg[maxn];
public:
    bool canFinish(int n, vector<vector<int>>& pre) 
    {
        int i;
        queue<int> q;
        for(i = 0; i < n; ++i) 
        {
            edges[i].clear();
            deg[i] = 0;
        }
        for(i = 0; i < pre.size(); ++i)
        {
            edges[ pre[i][1] ].push_back(  pre[i][0] );
            ++deg[ pre[i][0] ];
        }
        for(i = 0; i < n; ++i) 
        {
            if(0 == deg[i]) 
            {
                q.push(i);
            }
        }
        while(!q.empty()) 
        {
            int u = q.front();
            q.pop();
            for(i = 0; i < edges[u].size(); ++i) 
            {
                int v = edges[u][i];
                if(--deg[v] == 0 ) 
                {
                    q.push(v);
                }
            }
        }
        for(i = 0; i < n; ++i) 
        {
            if(deg[i]) 
            {
                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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50