一霎荷塘过雨
明朝便是秋声
C++，图，拓扑排序。
很经典的拓扑排序题，有向图，判断是否有环。
需要修完所有预修课，才能修当前课，就相当于图中要遍历所有前置结点，才能遍历当前结点，这就是拓扑排序。
思路也很简单：
- 建立邻接表，使用vector很容易建立
- 记录所有的入度，即
rudu[i]++ - 进入循环，深搜遍历所有入度为0的结点
- 深搜过程中，对于当前结点的邻接点，使用
rudu[next]--来减少入度 - 深搜过程中，如碰到了入度为0的；邻接点，则递归进入该结点
- 深搜过程中，对于当前结点的邻接点，使用
- 当所有结点都被遍历的时候，就说明无环，返回
true - 当一次循环完成，仍存在入度大于0的结点，说明有环，返回
false
比较简单的图论题。
代码如下：
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>> &prerequisites) {
vector<int> rudu(numCourses, 0);
vector<vector<int>> g(numCourses);
int ans = false;
for (int i = 0; i < prerequisites.size(); i++) {
vector<int> v = prerequisites[i];
rudu[v[1]]++;
g[v[0]].push_back(v[1]);
}
while (true) {
bool flag = true;
int cnt = numCourses;
for (int i = 0; i < numCourses; i++) {
if (rudu[i] == 0) {
flag = false;
dfs(i, g, rudu);
}
if (rudu[i] < 0) cnt--;
}
if (cnt == 0) ans = true;
if (flag || ans) break;
}
return ans;
}
void dfs(int root, vector<vector<int>> &g, vector<int> &rudu) {
rudu[root]--;
for (int next : g[root]) {
rudu[next]--;
if (rudu[next] == 0)
dfs(next, g, rudu);
}
}
};
