<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:
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        # 理论上两种情况的都是不行的
        # 一种是发现当前边有公共根节点
        # 一种是当前节点已有根
        # 其实是一种情况的两种发现顺序？
        # 当然如果你一直遍历下去。第二种情况是必然发现的，而第一种要取决于顺序，所以我们选择用第二种来判断。

        # 应该说存在两种环
        # 第一种是循环环，第二种是双根节点的环

        n = len(edges)
        parent = {}
        candA, candB = None, None
        root = list(range(n + 1))
        # 一个点指向多个点是无所谓的
        # 但是如果多个点指向一个点则返回
        # p存储的值是不是也要多个了

        for u, v in edges: # 这里肯定只有一组
            if v in parent: # 也就是我们说的第二种情况
                candA = [parent[v], v] # 旧边  
                candB = [u, v] # 新边 
                break
            parent[v] = u # 表示为v的根是u
        # 我们要移除的不是A就是B

        def find(x):
            if root[x] != x:
                root[x] = find(root[x])
            return root[x]

        for u, v in edges:
            # 注意这个肯定是出现在A后所以如果有问题了，A这里肯定会发现环，那么我们应该丢弃A
            if [u, v] == candB: # 因为他要求最后一条，所以我们优先丢B而不是A
                continue
            pu = find(u) # 都用find这样顺序性就不重要了
            pv = find(v)
            if pu == pv: # 环形结构
                if not candA: # 说明不存在双根
                    return [u, v]  # 返回最后发现环的位置
                return candA # 为什么这里意味着新边一定参与到环里了呢 因为新边一定不对？
            root[pv] = pu
        return candB #说明这个冗余新边不构成环

        # 我们并不一定能保证丢了边就一定有效了，但是双边中的某条边是一定要丢的
        # 那么就变成了选取问题了
        # 先发现问题一定要先丢，因为后面的边不能解决前面的问题，已经构成环了

        # 环形结构他只能检测顺序环，不能检测这种非循环的环 （应该说他要看访问顺序
        # 首先明确一个点，环由子节点指向他的祖先节点构成
        # 所以只要这个节点不是根节点，那就一定会造成双父节点
        # 所以情况如下
        # 1. 我们没有找到双重父节点，那么像无向版一样正常处理环就行了
        # 2. 有双父但是没有环，那肯定是移除A或B中的一根，B新移除B
        # 3. 是否说明新旧根本不重要
        # 我们直接丢掉一个边
        # 如果还存在环那说明丢错了
        # 如果不存在环了，那就丢这个
17100