Class Solution

01. Graphs/07. DSU/2. Redundant Connection II.cpp:14–64

class Solution {
public:
    int *p,*r;
    int find(int x) {
        if(p[x]==x) return x;
        return p[x]=find(p[x]);
    }
    void unite(int x,int y) {
        x=find(x);
        y=find(y);
        if(x==y) return ;
        if(r[x]>r[y]) {
            p[y]=x;
            r[x]++;
        } else {
            p[x]=y;
            r[y]++;
        }
    }
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<int> inDegree(n+1,-1);
        int rem1=-1,rem2=-1;
        for(int i=0;i<edges.size();i++) {
            vector<int> e=edges[i];
            if(inDegree[e[1]]!=-1) {
                rem2=i;
                rem1=inDegree[e[1]];
            }
            inDegree[e[1]]=i;
        }

        p = new int[n+1];
        r = new int [n+1];
        for(int i=0;i<n+1;i++) {
            p[i]=i;
            r[i]=0;
        }
        int flag =1;
        for(int i=0;i<edges.size();i++) {
            if(rem2 == i) continue;
            if(find(edges[i][0])==find(edges[i][1])) {
                if(rem1!=-1)return edges[rem1];
                else return edges[i];
            }
            unite(edges[i][0],edges[i][1]);
        }
        return edges[rem2];
        
    }
};