261. Graph Valid Tree

Given n nodes labeled from 0 to n-1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

Example 1:

Input: n = 5, and edges = [[0,1], [0,2], [0,3], [1,4]]
Output: true

Example 2:

Input: n = 5, and edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
Output: false

Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0,1] is the same as [1,0] and thus will not appear together in edges.

解题要点：

使用并查集，如两个点已经连上，则返回False。最后检查n，如果全部连上则n应该等于1，返回True，否则返回False。

class Solution(object):
    def validTree(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: bool
        """
        def find(edges, i):
            while i != edges[i]:
                i = edges[i]
                edges[i] = edges[edges[i]]
            return i
        
        def connected(edges, i, j):
            return find(edges, i) == find(edges, j)
        
        def union(edges, i, j):
            rooti = find(edges, i)
            rootj = find(edges, j)
            edges[rooti] = rootj
            
        res = [i for i in range(n)]
        for i, j in edges:
            if not connected(res, i, j):
                union(res, i, j)
                n -= 1
            else:
                return False
        if n == 1:
            return True
        else:
            return False