<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>

"""
In the original graph, if you add one edge, you either:
1. Keep a root and have a node with 2 parents
2. Created a cycle with the root

- So we will search the graph to handle either of these edge cases (e.g. detect 2 parents or detect cycle). You could have a cycle *and* 2 parents, so let's look for that as well.
--- 1 ---
- Finding 2 incoming edges is easy by iterating over edges list. When you find the node, how do you know which to remove?
- if there is no cycle, you can remove either
- if there is a cycle, remove the edge that maintains the connecteedness of the graph / breaks the cycle

--- 2 ---

- remove any edge that maintains the connectedness of the graph / breaks the cycle (e.g. any edge along the cycle)


so how to find nodes contained in a cycle
- do a DFS, starting from each node until you hit a cycle, then every node on the path starting from the dupe node is in the cycle
"""
class Solution:
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        graph = {}
        parent_vertices = list()
        child_vertices = list()
        for u, v in edges:
            parent_vertices.append(u)
            child_vertices.append(v)
            graph.setdefault(u, []).append(v)
        
        root_nodes = set(parent_vertices) - set(child_vertices)

        visited = set()
        cycle_edges = set()
        def search(node):
            if node in visited:
                return True
            visited.add(node)
            for child in graph.get(node, []):
                if search(child):
                    cycle_edges.add((node, child))
            visited.remove(node)

        found_cycle = False
        for node in parent_vertices:
            search(node)
        
        # print(cycle_edges)
        if root_nodes:
            counts = Counter(child_vertices)
            double_child = next(v for v in counts if counts[v] == 2)
            if cycle_edges:
                return next((
                    [u,v]
                    for u,v in cycle_edges
                    if v == double_child
                ), None)
            else:
                return [
                    [u,v]
                    for u,v in edges
                    if v == double_child
                ][-1]
        else:
            return [edge for edge in edges if tuple(edge) in cycle_edges][-1]

        

17900