684. 冗余连接

• 思路
  • example
  • 并查集

并查集主要有三个功能。
寻找根节点，函数：find(int u)，也就是判断这个节点的祖先节点是哪个
将两个节点接入到同一个集合，函数：join(int u, int v)，将两个节点连在同一个根节点上
判断两个节点是否在同一个集合，函数：same(int u, int v)，就是判断两个节点是不是同一个根节点

例2，edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
ancestor = [0, 1, 2, 3, 4, 5], i.e., ancestor[i] = i
edge = [1,2], find(1), find(2), ancestor[find(1)] = ancestor[find(2)], ancestor = [0, 2, 2, 3, 4, 5].
edge = [2,3], find(2), find(3), ancestor[find(2)] = ancestor[find(3)], ancestor = [0, 2, 3, 3, 4, 5].
edge = [3,4], find(3), find(4), ancestor[find(3)] = ancestor[find(4)], ancestor = [0, 2, 3, 4, 4, 5].
edge = [1,4], find(1), find(4), ancestor = [0, 4, 4, 4, 4, 5] (注意这里，把节点1，2，3的ancestor都改为了4). find(1) = find(4) = 4， 找到loop, 删掉这个edge即可
edge = [1,5], 不需要处理

另一个例子
edges = [[1,2], [2,3], [3,4], [2,5]]
ancestor = [0, 1, 2, 3, 4, 5], i.e., ancestor[i] = i
edge = [1,2], find(1), find(2), ancestor[find(1)] = ancestor[find(2)], ancestor = [0, 2, 2, 3, 4, 5].
edge = [2,3], find(2), find(3), ancestor[find(2)] = ancestor[find(3)], ancestor = [0, 2, 3, 3, 4, 5].
edge = [3,4], find(3), find(4), ancestor[find(3)] = ancestor[find(4)], ancestor = [0, 2, 3, 4, 4, 5].
edge = [2,5], find(2), find(5), ancestor[find(2)] = ancestor[find(5)], ancestor = [0, 4, 4, 4, 5, 5].

• 复杂度. 时间：O(?), 空间: O(?)

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        parent = list(range(n+1)) # e.g., parent[1] = 1
        def find(node): # 递归, 寻找祖先，并且在寻找的同时把上辈节点全部指向祖先节点 (只需要第一遍连接，后续调用只需最多二步)
            if parent[node] != node: 
                parent[node] = find(parent[node]) # node的parent 就是node的parent的 祖先
            return parent[node] 
        def union(node1, node2): # node1的祖先 指向 node2的祖先
            parent[find(node1)] = find(node2)
        # main code 
        for i in range(len(edges)):
            node1, node2 = edges[i][0], edges[i][1]
            if find(node1) != find(node2): # 
                union(node1, node2)
            else: # already find a loop, edges[i] is redundant 
                return edges[i]   

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        def find(u):
            if ancestor[u] != u:
                ancestor[u] = find(ancestor[u])
            return ancestor[u] 
        def join(u, v):
            ancestor[find(u)] = find(v) 
        def same(u, v):
            return find(u) == find(v) 
        # 
        n = len(edges) 
        ancestor = [i for i in range(n+1)]  
        for edge in edges:
            u, v = edge[0], edge[1] 
            if same(u, v):
                return edge 
            join(u, v) 

• DFS (无向图，检测某条边是否是环的一部分)

例2, edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
先构造graph:
graph[1] = [2, 4, 5]
graph[2] = [1, 3]
graph[3] = [2, 4]
graph[4] = [1, 5]
graph[5] = [1]
倒序dfs遍历edges, 判断：
edge = [1,5], edge[1] = 5, neighbors = [] (不包括edge[0])
edge = [1, 4], edge[1] = 4, neighbors = [5, 1, 2, 3], edge[0] in neighbors: 环

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        def dfs(graph, parent, x, y): 
            visited.add(x)
            for node in graph[x]:
                if node == y and x != parent: # 保证[x,y] != [parent, y] (起始边）
                    return True
                if node not in visited:
                    if dfs(graph, parent, node, y) == True:
                        return True 
            return False 
        graph = collections.defaultdict(list)
        for edge in edges: 
            x, y = edge[0], edge[1]
            graph[x].append(y)
            graph[y].append(x) 
        for i in range(len(edges)-1, -1, -1):
            x, y = edges[i][0], edges[i][1] 
            visited = set() #!!!
            visited.add(y) # !!!!!!
            if dfs(graph, x, x, y) == True:
                return edges[i] 

• 或者顺序遍历edges，逐次加进graph，DFS (这个效率更高)

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        graph = {}
        
        def dfs(u, v):
            visited.add(u)    # u当作是起点
            for node in graph[u]:
                if node == v:     # 已经找到环    
                    return True
                elif node not in visited:
                    if dfs(node, v):   
                        return True 
            return False

        for edge in edges:
            if edge[0] not in graph:
                graph[edge[0]] = {edge[1]}  
            else:
                visited = set()
                if dfs(edge[0], edge[1]):
                    return edge
                else:
                    graph[edge[0]].add(edge[1])
            if edge[1] not in graph:
                graph[edge[1]] = {edge[0]}
            else:
                graph[edge[1]].add(edge[0])