leetcode207. 课程表

题目

题解

对于含有环的图肯定是不可能实现的，构建拓扑排序

const int N = 2010;
class Solution {
public:
    int ne[N*2], e[N*2],idx,h[N],d[N],q[N];
    void add(int a, int b){
        ne[idx] = h[a];
        e[idx] = b;
        h[a] = idx++;
    }
    bool top_sort(int numCourses){
        int hh = 0, tt = -1;
        for(int i=0;i<numCourses;i++){
            if(d[i]==0) q[++tt] = i;
        }
        while(hh<=tt){
            int t = q[hh++];
            for(int i = h[t]; i != -1; i = ne[i]){
                int j = e[i];
                if(--d[j]==0) q[++tt] = j;
            }
        }
        return tt == numCourses-1;
    }
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        memset(h, -1, sizeof h);
        memset(d, 0, sizeof d);
        for(auto t:prerequisites){
            add(t[0],t[1]);
            d[t[1]]++;
        }
        return top_sort(numCourses);
    }
};