算法1

并查集

Python3代码

class Solution:
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        # 方法一： 有向图的并查集
        # 1. 初始化每个点的父节点是自己
        parent = [n for n in range(len(edges)+1)]
        recoder = parent[:]
        def findParent(x):
            if parent[x] != x:
                parent[x] = findParent(parent[x])
            return parent[x]
        # 有两种情况：1.冗余的边指向根节点---会有环: parent[x] = parent[y]， 用circle记录
        #            2. 冗余的边指向非根节点----非根节点入度为2: parent[x]!=x， 用conflict记录, 一个节点既是环又是冲突，优先记为冲突，如[[3,1],[2,1],[4,2],[1,4]]，那么后面就不会再有环
        conflict = -1
        circle = -1
        for i, (node1,node2) in enumerate(edges):
            if parent[node2] != node2:
                # 当前子节点入度为2，记为冲突节点
                conflict = i
            else:
                recoder[node2] = node1
                root_x = findParent(node1)
                root_y = findParent(node2)
                if root_x == root_y:
                    # 存在环
                    circle = i
                else:
                    parent[root_y] = root_x
        # 1. 无冲突边，直接返回环
        if conflict < 0:
            return edges[circle]
        # 2. 有冲突边，无环,直接返回冲突边
        elif circle < 0:
            return edges[conflict]
        # 3. 有冲突，有环，返回冲突边同子节点的另一条边
        else:
            u = edges[conflict][1]
            return [recoder[u], u]

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla