拓扑排序

一、定义

拓扑排序是对一个有向图构造拓扑序列，解决工程是否能顺利进行的问题。

二、代码实现

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
class Solution {
private:
    vector<vector<int>> edges;
    vector<int> visited;
    bool valid = true;

public:
    void dfs(int u) {
        visited[u] = 1;
        for (int v: edges[u]) {
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            }
            else if (visited[v] == 1) {
                valid = false;
                return;
            }
        }
        visited[u] = 2;
    }

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses);
        visited.resize(numCourses);
        for (const auto& info: prerequisites) {
            edges[info[1]].push_back(info[0]);
        }
        for (int i = 0; i < numCourses && valid; ++i) {
            if (!visited[i]) {
                dfs(i);
            }
        }
        return valid;
    }
};


class Solution {
public:
    vector<vector<int>> edges;
    vector<int> numedegs;

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses);
        numedegs.resize(numCourses);
        for(auto &info : prerequisites)
        {
            edges[info[1]].push_back(info[0]);
            ++numedegs[info[0]];//info[0]还有多少个先修课程
        }
        queue<int>q;
        for(int i = 0;i < numCourses; i++)
        {
            if (numedegs[i] == 0 )
                q.push(i);
        }
        int visited = 0;
        while(!q.empty())
        {
            ++visited;
            int u = q.front();
            q.pop();
            for(auto & v: edges[u])
            {
                --numedegs[v];
                if(numedegs[v] == 0)
                    q.push(v);
            }
        }
        return visited == numCourses;
    }
};