<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 DisjointSet
{
    public:
    vector<int> size, parent;
    DisjointSet(int n)
    {
        size.resize(n + 1, 1);
        parent.resize(n + 1);

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

    int findUPar(int node)
    {
        if(node == parent[node])
        return node;

        return parent[node] = findUPar(parent[node]);
    }

    void unionBySize(int u, int v) 
    {
        int ulp_u = findUPar(u);
        int ulp_v = findUPar(v);

        // no need to join them anymore
        if (ulp_u == ulp_v) 
        return;

        if (size[ulp_u] < size[ulp_v]) 
        {
            parent[ulp_u] = ulp_v;
            size[ulp_v] += size[ulp_u];
        }

        else 
        {
            parent[ulp_v] = ulp_u;
            size[ulp_u] += size[ulp_v];
        }
    }
};

class Solution {
public:
    void dfsCheck(int node, vector<vector<int>> &adj, vector<bool> &vis, vector<int> &toIgnore)
    {
        vis[node] = true;
        for(int &child: adj[node])
        {
            if(node == toIgnore[0] && child == toIgnore[1])
            continue;

            if(!vis[child])
            dfsCheck(child, adj, vis, toIgnore);
        }
    }

    vector<int> findEdge(vector<vector<int>> &edges)
    {
        int n = edges.size();
        DisjointSet ds(n);

        for(auto &vec: edges)
        {
            int from = vec[0], to = vec[1];
            if(ds.findUPar(from) == ds.findUPar(to))
            return {from, to};

            ds.unionBySize(from, to);
        }

        return {};
    }

    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) 
    {
        int n = edges.size(); // same as number of edges, since a tree has n - 1 edges

        // 2 cases: If root has 1 indegree (1 parent), and if a node has 2 parents
        // case 1: Removing any edge in a cycle still keeps the graph traversible.

        // case 2: Can't randomly remove a edge because it might be the case that removing an edge  
        // makes the graph disconnected. Need DFS from root to verify if graph is still traversible to all nodes

        vector<int> indegree(n + 1, 0);
        vector<vector<int>> adj(n + 1);

        for(auto &vec: edges)
        {
            int from = vec[0];
            int to = vec[1];

            adj[from].push_back(to);
            ++indegree[to];
        } 

        int root = -1, two = -1;
        for(int i=1; i<=n; i++)
        {
            if(indegree[i] == 0)
            root = i;

            else if(indegree[i] == 2)
            two = i;
        }

        // root has an indegree
        if(root == -1)
        {
            // use disjoint set to find out the last redundant edge. Return that
            return findEdge(edges);
        }

        // some other node has indegree = 2
        // preference will be given to 2nd edge of reqdEdge since that occurred last
        // remove that edge and check if tree is traversible from root
        vector<vector<int>> reqdEdge;
        for(auto &vec: edges)
        {
            int from = vec[0], to = vec[1];
            if(to == two)
            reqdEdge.push_back(vec);
        }

        vector<int> toIgnore = reqdEdge[1];
        vector<bool> vis(n + 1, false);

        dfsCheck(root, adj, vis, toIgnore);
        for(int i=1; i<=n; i++)
        {
            // if any node not visited, first edge is the answer
            if(!vis[i])
            return reqdEdge[0];
        }

        return reqdEdge[1];
    }
};
13903