685

class Solution {
public:
vector<int> parent;
public:
    int findParent(int x){
        return (parent[x] == x) ? x: (parent[x] = findParent(parent[x]));
    }

    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        parent.resize(n+1, 0);
        vector<int> p1, p2;

        /// There are 2 possibilities of flaw edge:
        // 1. One which makes a node have 2 parents.
        // 2. One which forms a cycle in tree.

        for(auto &edge: edges){
            if(parent[edge[1]] == 0)
                parent[edge[1]] = edge[0];
            else{
                p1 = {parent[edge[1]], edge[1]};
                p2 = edge;
                edge[1] = 0; // Virtually remove edge making a node have 2 parents.
            }
        }

        for(int i=1; i<=n; i++)
            parent[i] = i;

        // Now each node has only 1 parent. So the possibility of 2 parents is gone.
        // If a cycle is found now, return p1 if it exists, else return the edge forming cycle.
        for(auto edge: edges){
            if(edge[1] == 0) continue;
            int x = edge[0]; int y = edge[1];
            int px  = findParent(edge[0]);
            if(px == y){
                if(p1.size()) return p1;
                return edge;
            }
            parent[y] = px;
        }
        // If things go fine, our assumption of removing earlier edge was right, so return that edge.
        return p2;
    }
};