leetcode207.课程表（判断有向图是否有环）

207. 课程表

方法一：拓扑排序

class Solution {
    
public:

    vector<vector<int>> get_adj_list(int numCourses,vector<vector<int>> &prerequisites){
    
        //获得图的邻接表
        vector<vector<int>> graph(numCourses);

        for(auto &e:prerequisites){
    
            graph[e[0]].push_back(e[1]);
        }

        return graph;
    }

    bool topo_sort(vector<vector<int>> &graph){
    
        //拓扑排序判断是否有环
        
        int cnt=0;//拓扑序列中的顶点个数
        int num_v=graph.size();//图中顶点个数
        vector<int> deg(num_v);//各个顶点的度

        stack<int> st;//存入度为0的顶点
        
        //计算各个顶点的度
        for(int i=0;i<num_v;i++){
    
            for(auto &v:graph[i]){
    
                deg[v]++;
            }
        }

        //将入度为0的顶点入栈
        for(int i=0;i<deg.size();i++){
    
            if(deg[i]==0){
    
                st.push(i);
            }
        }

        while(!st.empty()){
    
            int v=st.top(); //顶点v
            st.pop();
            cnt++;

            for(auto &i:graph[v]){
    
                //去掉顶点v看看是否会产生度为0的顶点
                deg[i]--;
                if(deg[i]==0){
    
                    st.push(i);
                }
            }
        }

        if(cnt<num_v){
    
            return false;
        }
        else{
    
            return true;
        }

    }

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    
        auto adj_list=get_adj_list(numCourses,prerequisites); 
        return topo_sort(adj_list);
    
    }
};

方法二：dfs深搜

class Solution {
    
public:

    vector<vector<int>> get_adj_list(int numCourses,vector<vector<int>> &prerequisites){
    
        //获得图的邻接表
        vector<vector<int>> graph(numCourses);

        for(auto &e:prerequisites){
    
            graph[e[0]].push_back(e[1]);
        }

        return graph;
    }

    void dfs(vector<vector<int>> &graph,int u,vector<int> &vis,vector<int> &in_dfs,bool &loop){
    
        
        if(loop){
    
            //检测到环
            return ;
        }

        in_dfs[u]=1;
        vis[u]=1;
        for(auto &v:graph[u]){
    
            if(in_dfs[v]){
    
                //如果这个顶点在本次dfs中
                loop=true;
                return ;
            }
            if(!vis[v]){
    
                //如果这个顶点还未访问过
                dfs(graph,v,vis,in_dfs,loop);        
            }
        }
        in_dfs[u]=0;
    }

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    
        auto graph=get_adj_list(numCourses,prerequisites); 
        vector<int> vis(numCourses);
        vector<int> in_dfs(numCourses);  
        bool loop=false;
        for(int i=0;i<numCourses;i++){
    
            if(!vis[i]){
    
                dfs(graph,i,vis,in_dfs,loop);
                if(loop){
    
                    break;
                }
            }
        }

        return !loop;
    }
};