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.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Hint:

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree?

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.

Solution: Union-find

class Solution(object):
    def validTree(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: bool
        """
        if n != len(edges) + 1:
            return False
        unions = [-1] * n
        for left, right in edges:
            left_root = self.find(left, unions)
            right_root = self.find(right, unions)
            if left_root == right_root:
                return False
            unions[left_root] = right_root
        return True

    def find(self, num, unions):
        root = num
        while root != unions[root] >= 0:
            root = unions[root]
        unions[num] = root
        return root

Lessons:

• n == len(edges) + 1 guarantees all nodes are connected once.
• If both ends of a new edge are already in the same union, there is a circle.
• find also creates a new union when see a new number.