<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 Solution {
public:
    /*
    a rooted tree
        -> every node has one parent except root node
    edge in edges
        edge[u, v] means node u is parent of node v
                             u -> v

    1   -->  3
    |       ^
    v      /
    2   --
    we can remove the 1 -> 3 & 2 -> 3
    we can't remove the 1 -> 2 edge, otherwise there will be two parents
    1 -> 3
         ^
        /
    2 -
    out_degree
        1   2   3
        1   1   0
    form the adj_list
    */

    bool IsValidTree(const vector<vector<int> > &adj_list, 
                     const int ignore_source,
                     const int ignore_dest,
                     vector<int> &degrees)
    {
        std::queue<int> q;
        for (int i = 0; i < degrees.size(); ++i)         
        {
            if (degrees[i] == 0)
                q.push(i);
        }
        int set_cnt = adj_list.size();

        int connected_cnt = 0, root_cnt = 0, visited_cnt = 0;
        //std::cout << "Ignore " << ignore_source << " -> " << ignore_dest << ": " << root_cnt << std::endl;
        while (q.size())
        {
            int id = q.front();
            visited_cnt++;
            //std::cout << id << std::endl;
            q.pop();
            connected_cnt = 0;
            for (auto parent : adj_list[id])
            {
                if (id == ignore_source && parent == ignore_dest) continue;
                connected_cnt++;
                degrees[parent]--;
                if (degrees[parent] == 0)
                {
                    q.push(parent);
                }
            }
            if (connected_cnt > 1) return false;
            root_cnt += (connected_cnt == 0);
        }
        //std::cout << "Result: " << root_cnt << ", " << visited_cnt << std::endl;
        return root_cnt == 1 && visited_cnt == adj_list.size() - 1;
    }


    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) 
    {
        vector<vector<int> > adj_list(edges.size() + 1);
        vector<int> degrees(edges.size() + 1, 0);
        for (auto &edge : edges)
        {
            adj_list[edge.back()].push_back(edge.front());
            degrees[edge.front()]++;
        }
        degrees[0] = INT_MIN;
        vector<int> ret;
        for (auto &edge : edges)
        {
            int u = edge.front();
            int v = edge.back();
            vector<int> temp_degree = degrees;
            temp_degree[u]--;
            if (IsValidTree(adj_list, v, u, temp_degree))
                ret = edge;
        }
        return ret;
    }
};
53446