class UnionFind:
    def __init__(self, n):
        self.father = [i for i in range(n)]
        self.count = n

    def find(self, x):
        if self.father[x] == x:
            return x
        return self.find(self.father[x])

    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a != root_b:
            self.father[root_a] = root_b
            self.count -= 1


class Solution:
    """
    @param n: An integer
    @param edges: a list of undirected edges
    @return: true if it's a valid tree, or false
    """
    # 以图的视角来看树：树是一张连通的无向无环图（N个结点有N - 1条边)
    # 满足一下三个条件中的两个，那么这个图就是树
    # 1）边树 == 结点数 - 1
    # 2）无环
    # 3）所有点都连通（连通分量的个数为1）
    def validTree(self, n, edges):
        # write your code here
        # 满足1）
        if len(edges) != n - 1:
            return False

        uf = UnionFind(n)

        for i in range(len(edges)):
            uf.union(edges[i][0], edges[i][1])
        # 满足3）
        return uf.count == 1

    # meet 1) and 2)
    def validTree2 (self, n, edges):
        # write your code here
        if len(edges) != n - 1:
            return False
        uf = UnionFind(n)

        for edge in edges:
            src = edge[0]
            dst = edge[1]
            # 检查这两个点是否在一个连通图中，如果在，已经在了，再有一条边，说明有环
            root0 = uf.find(src)
            root1 = uf.find(dst)
            # edge[0] and edge[1]已经连通了
            if root0 == root1:
                return False
            # 如果不在一个通联图中，那么把两个点连通起来
            uf.union(src, dst)
        return True
