<p>In this problem, a rooted tree is a <b>directed</b> graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.</p>

<p>The given input is a directed graph that started as a rooted tree with <code>n</code> nodes (with distinct values from <code>1</code> to <code>n</code>), with one additional directed edge added. The added edge has two different vertices chosen from <code>1</code> to <code>n</code>, and was not an edge that already existed.</p>

<p>The resulting graph is given as a 2D-array of <code>edges</code>. Each element of <code>edges</code> is a pair <code>[u<sub>i</sub>, v<sub>i</sub>]</code> that represents a <b>directed</b> edge connecting nodes <code>u<sub>i</sub></code> and <code>v<sub>i</sub></code>, where <code>u<sub>i</sub></code> is a parent of child <code>v<sub>i</sub></code>.</p>

<p>Return <em>an edge that can be removed so that the resulting graph is a rooted tree of</em> <code>n</code> <em>nodes</em>. If there are multiple answers, return the answer that occurs last in the given 2D-array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/12/20/graph1.jpg" style="width: 222px; height: 222px;" />
<pre>
<strong>Input:</strong> edges = [[1,2],[1,3],[2,3]]
<strong>Output:</strong> [2,3]
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/12/20/graph2.jpg" style="width: 222px; height: 382px;" />
<pre>
<strong>Input:</strong> edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]
<strong>Output:</strong> [4,1]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == edges.length</code></li>
	<li><code>3 &lt;= n &lt;= 1000</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>1 &lt;= u<sub>i</sub>, v<sub>i</sub> &lt;= n</code></li>
	<li><code>u<sub>i</sub> != v<sub>i</sub></code></li>
</ul>


class DSU {

    public :

    vector<int> par; 
    vector<int> rank; // based on size.

    DSU(int n){
        par.resize(n);
        for(int i=0;i<n;i++) par[i]=i;
        for(int i=0;i<n;i++) rank.push_back(1);
    }

    bool unite(int u,int v){
        
        int root1 = find_par(u);
        int root2 = find_par(v);

        if(root1==root2) return false; // forms a cycle.

        if(rank[root1]<rank[root2]) swap(root1,root2);

        par[root2] = root1;
        rank[root1] += rank[root2];

        return true; //succesfully united
    }

    int find_par(int u){
        if(par[u]==u) return u;
        return par[u] = find_par(par[u]);
    }

};



class Solution {

public:
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        
        // 3 <= n <= 1000   =>  Even O(N^2) would be fine.

        // Basically after removing every edge check if it's a rooted tree ?.
        // First of all, we can root any tree arbitrarily about any node, so
        // we just need to verify it's a tree as every tree can be thought of
        // as a rooted tree ?.

        // No, I think direction mttrs, as we're gn directed edges !.

        //     4
        // 3   2
        //   1

        int n = 1;
        int m = edges.size();

        for(auto x : edges){
            auto [u,v] = make_pair(x[0],x[1]) ;
            n = max({n,u,v});
        }







        // Think in reverse ?. Adding instead of removing ?.

        // Failed Attempt :

        /*
        // Is single CC with n-1 nodes, sufficient condn for a rooted tree ?.

        for(int i=m-1;i>=0;i--){

            bool f = true;

            DSU dsu(n);

            for(int j=0;j<m;j++){
                if(j==i) continue;
                f &= dsu.unite(edges[j][0]-1,edges[j][1]-1);
            }

            if(f) return edges[i];
        }

        return {-1,-1};

        */

        // Another Attempt :
        // Did the same, won't work cuz it's not undirected, it's a directed graph !.
        
        // But I think, just adding one more condition would make it work.
        // I.e indeg should be 0 for only one node, and it must be 1 for all other nodes.

        // /*
        for(int i=m-1;i>=0;i--){ // i is the edge we exclude.

            DSU dsu(n);

            vector<int> indeg(n,0);

            for(int j=0;j<m;j++){
                if(j==i) continue;
                indeg[edges[j][1]-1]++;
                dsu.unite(edges[j][0]-1,edges[j][1]-1);
            }

            set<int> st;

            for(int i=0;i<n;i++){
                st.insert(dsu.find_par(i));
            }

            bool condn = true; int cnt = 0;
            for(int i=0;i<n;i++){
                if(indeg[i]!=0 && indeg[i]!=1) condn = false;
                cnt += indeg[i]==0 ;
            }
            condn &= (cnt==1) ;
            
            if(st.size()==1 && condn){
                return edges[i];
            }

        }

        return {-1,-1};
        // */


        

    }
};
56653