LeetCode 261 [Graph Valid Tree]

原题

给出 n 个节点，标号分别从 0 到 n - 1 并且给出一个 无向 边的列表 (给出每条边的两个顶点), 写一个函数去判断这张｀无向｀图是否是一棵树

样例
给出n = 5 并且 edges = [[0, 1], [0, 2], [0, 3], [1, 4]], 返回 true.
给出n = 5 并且 edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], 返回 false.

解题思路

• 判断输入的边，是否能构成树看两点：
• 是否有环，有环则不是树
• 是否所有点最终都相连，有不相连则不是树
• 集合合并问题，使用并查集
• 如果合并的时候发现两个点的father一样，则有环
• 最终统计father的个数，超过一个说明没有全部相连

完整代码

class UnionFind:
    def __init__(self, n):
        self.father = {}
        for i in range(n):
            self.father[i] = i 
  
    def compressed_find(self, x):
        parent = self.father[x]
        while parent != self.father[parent]:
            parent = self.father[parent]

        temp = -1;
        fa = self.father[x]
        while fa != self.father[fa]:
            temp = self.father[fa]
            self.father[fa] = parent
            fa = temp

        return parent

        
    def union(self, x, y):
            fa_x = self.compressed_find(x)
            fa_y = self.compressed_find(y)
            if fa_x != fa_y:
                self.father[fa_x] = fa_y

class Solution:
    # @param {int} n an integer
    # @param {int[][]} edges a list of undirected edges
    # @return {boolean} true if it's a valid tree, or false
    def validTree(self, n, edges):
        # Write your code here
        if len(edges) != n - 1:
            return False
            
        uf = UnionFind(n)
        
        for edge in edges:
            pointA, pointB = edge[0], edge[1]
            fpointA = uf.compressed_find(pointA)
            fpointB = uf.compressed_find(pointB)
            if fpointA == fpointB:
                return False
            else:
                uf.union(pointA, pointB)
                
        return True