图、图的遍历及图的拓扑排序

Node* head[MAX_N];

node->to = y;

node->next = head[x];

head[x]=node;

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        to = vector<vector<int>>(numCourses, vector<int>());
        inDeg = vector<int>(numCourses, 0);
        for(vector<int>& pre : prerequisites) {
            int ai = pre[0];
            int bi = pre[1];
            to[bi].push_back(ai);
            inDeg[ai]++;
        }
        queue<int> q;
        for(int i = 0; i < numCourses; i++) {
            if(inDeg[i] == 0) q.push(i);
        }
        vector<int> lessons;
        while(!q.empty()) {
            int x = q.front();
            q.pop();
            lessons.push_back(x);
            for(int y : to[x]){
                inDeg[y]--;
                if(inDeg[y] == 0) {
                    q.push(y);
                }
            }
        }
        return lessons.size() == numCourses;
    }
private:
    vector<vector<int>> to;
    vector<int> inDeg;
};

class Solution {
private:
    vector<vector<int>> edge;
    vector<int> degree;
    vector<int> ans;
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        edge.resize(numCourses);
        degree.resize(numCourses);
        queue<int> q;
        for(auto tmp:prerequisites)
        {
            edge[tmp[1]].push_back(tmp[0]);
            degree[tmp[0]]++;
        }
        for(int i=0;i<numCourses;i++)
        {
            if(degree[i]==0)
            {
                q.push(i);
                ans.push_back(i);
            }
        }
        while(!q.empty())
        {
            int cur=q.front();
            q.pop();
            for(auto tmp:edge[cur])
            {
                degree[tmp]--;
                if(degree[tmp]==0)
                {
                    q.push(tmp);
                    ans.push_back(tmp);
                }
            }
        }
        if(ans.size()<numCourses)
        {
            return {};
        }
        return ans;
    }
};

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        n = 0;
        for(vector<int>& edge : edges) {
            int x = edge[0];
            int y = edge[1];
            n = max(n, max(x, y));
        }
        to = vector<vector<int>>(n + 1, vector<int>());
        visited = vector<bool>(n + 1, false);
        for(vector<int>& edge : edges) {
            int x = edge[0];
            int y = edge[1];
            to[x].push_back(y);
            to[y].push_back(x);
            hasCycle = false;
            for(int i = 1; i <= n; i++) visited[i] = false;
            dfs(x, 0);
            if(hasCycle) return edge;
        }
        return {};
    }
private:
    void dfs(int x, int fa) {
        visited[x] = true;
        for(int y : to[x]) {
            if(y == fa) continue;
            if(!visited[y]) dfs(y, x);
            else hasCycle = true;
        }
    }
    int n;
    vector<vector<int>> to;
    vector<bool> visited;
    bool hasCycle;
};

class Solution {
public:
    int find(int x){return parent[x]==x?x:find(parent[x]);}
    //void merge(int x,int y){ 正常并查集是需要单独一个merge函数的，但由于我们这里是树状的，可以省掉这个函数
    //    parent[x] = y;
    //}
    vector<int>parent;
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        parent.resize(edges.size()+1);
        for(int i=0;i<parent.size();i++) parent[i] = i;
        int conflict = -1;
        int cycle = -1;
        for(int i = 0;i<edges.size();i++){
            int a = edges[i][0];
            int b = edges[i][1];//此时a指向b  b要认a为父亲
            if(parent[b] != b)//冲突 b的父亲早就不是自己了
            {
                conflict = i;//找到了后一条冲突边
            }
            else
            {
                if(find(a) == find(b))//有循环，即能够查找到相同的祖先
                {
                    cycle = i;//记录出现循环的边
                }
                else parent[b] = a;//都不是的情况就让b的父节点是a
            }
        }
        //根据情况判断
        if(conflict < 0){//没有冲突边  纯循环，那么最后导致出现循环的边就是答案
            return vector<int>{edges[cycle][0],edges[cycle][1]};
        }
        else if(cycle >= 0){//有冲突边，也有循环边,那么除了冲突的的另一个父亲分支有问题
            auto c = edges[conflict];
            return vector<int>{parent[c[1]],c[1]};
        }
        else if(cycle < 0){//只有冲突边
            auto c = edges[conflict];
            return vector<int>{edges[conflict][0],edges[conflict][1]};
        }
        return {};
    }
};