有向图找环 拓扑排序

找环有几个问题，首先，是否要求找到所有的环？这个有点难，如果是完全图，那环太多了，只能暴力。

所以，此题仅限于找一个环。

平常加dp的话，用队列做还是很方便的，但是找环dfs是很在行的，此题用dfs记录路径即可。只需对原始的拓扑排序做一些修改即可。

class Solution {
map<int, vector<int>> v;
public:
    int dfs(vector<int>& F, vector<int>&path, int n)
    {
        if(F[n] == -1)return true;
        if(F[n] == 1)return false;
        F[n] = 1;
        path.push_back(n);
        for(int i=0;i<v[n].size();i++)
        {
            int ok = dfs(F, path, v[n][i]);
            if(!ok)return false;
        }
        F[n] = -1;
        path.pop_back();
        return true;
    }

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        for(auto t: prerequisites)
        {
            v[t[1]].push_back(t[0]);
        }
        vector<int> path, F(numCourses);
        for(int i=0;i<numCourses;i++)
        {
            int ok = dfs(F, path, i);
            if(!ok)
            {
                for(auto p: path)
                    printf("%d ", p);
                printf("\n");
                return false;
            }
        }
        return true;
    }
};