课程表 图解题解

# 「有依赖顺序，判能否排序 / 有无环」都套
indeg = [0]*n; g = defaultdict(list)
for u, v in 依赖: g[u].append(v); indeg[v] += 1   # u→v
q = deque(i for i in range(n) if indeg[i]==0)
cnt = 0
while q:
    x = q.popleft(); cnt += 1
    for y in g[x]:
        indeg[y] -= 1
        if indeg[y]==0: q.append(y)
return cnt == n        # 全出队才无环

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> indeg(numCourses, 0);
        for (auto& p : prerequisites) { graph[p[1]].push_back(p[0]); indeg[p[0]]++; }
        queue<int> q;
        for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.push(i);
        int seen = 0;
        while (!q.empty()) {
            int cur = q.front(); q.pop(); seen++;
            for (int nxt : graph[cur]) if (--indeg[nxt] == 0) q.push(nxt);
        }
        return seen == numCourses;
    }
};

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
        int[] indeg = new int[numCourses];
        for (int[] p : prerequisites) { graph.get(p[1]).add(p[0]); indeg[p[0]]++; }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.offer(i);
        int seen = 0;
        while (!q.isEmpty()) {
            int cur = q.poll(); seen++;
            for (int nxt : graph.get(cur)) if (--indeg[nxt] == 0) q.offer(nxt);
        }
        return seen == numCourses;
    }
}