很显然的拓扑排序

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {int n = numCourses;vector<int> record(n+1,0);queue<int> q;vector<vector<int>> graph(n + 1);for (int i = 0; i < prerequisites.size(); i++) {int now = prerequisites[i][0];for (int j = 1; j < prerequisites[i].size();j++) {record[now]++;graph[prerequisites[i][j]].push_back(now);  // 还是建一个图吧}//if(record[now]==0) q.push(now);}for (int i = 0; i < n; i++) {if (record[i] == 0) q.push(i);}if (q.size() == 0) return false;int cnt = 0;vector<int> vis(n + 1, 0);while (q.size()){int u = q.front(); q.pop();if (vis[u]) continue;vis[u] = 1; cnt++;for (auto v : graph[u]) {record[v]--; if (record[v] == 0) q.push(v);}}return cnt == n;}};

双倍经验