684.冗余连接

https://leetcode-cn.com/problems/redundant-connection/

一、并查集

模板

class UnionFind:
    # 构造函数传入totalNodes为总节点数
    def __init__(self, totalNodes):
        # parents[i]表示i的根，初始i的根为其自身
        self.parents = [i for i in range(totalNodes+1)]
        # 连通分量数
        self.count = totalNodes
        # 连通分量大小，即树的“重量”
        self.size = [1] * (totalNodes+1)
    # 合并连通区域是通过find来操作的, 即看这两个节点是不是在一个连通区域内.
    def union(self, node1, node2):
        root1 = self.find(node1)
        root2 = self.find(node2)
        # 不连通才合并
        if root1 != root2:
          	# 小树合并到大树
            if self.size[root1] > self.size[root2]:
                self.parents[root2] = root1
                self.size[root1] += self.size[root2]
            else:
                self.parents[root1] = root2
                self.size[root2] += self.size[root1]
            # 连通分量数减一
            self.count -= 1

    # 查找最终的根
    def find(self, node):
        while self.parents[node] != node:
            self.parents[node] = self.parents[self.parents[node]]
            node = self.parents[node]
        return node

    # 判断两个点是否连通
    def isConnected(self, node1, node2):
        return self.find(node1) == self.find(node2)

    # 返回连通分量个数
    def count(self):
        return self.count

尝试每次删除一条边（edges中靠后的边），用剩下的边构建图，连接边的两顶点，若最后只构成一个连通分量，说明剩余的边可以构成树（题目已说明图是由树加一条边构成）

注意顶点从1开始，并查集实现稍作修改，留0号节点不用

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        for i in range(n-1, -1, -1):
            leftEdges = edges[:i] + edges[i+1:]
            uf = UnionFind(n)
            for a, b in leftEdges:
                uf.union(a, b)
            if uf.count == 1:
                return edges[i]

改进：逆向思维

上面方法是按题意正向操作，其实不需要每次都用n-1条边构建图。

现在反过来，按edges顺序遍历，每次测试两端点a、b是否连通，若不连通则将其连通；若已连通，说明增加这条边就构成图，该边就是要找的边

# 并查集实现代码同上，略
class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        uf = UnionFind(n)
        for a, b in edges:
            if uf.isConnected(a, b):
                return [a, b]
            else:
                uf.union(a,b)