261.Graph Valid Tree

Tags: [union_find], [tree], [graph], [undirected_graph], [cycle], [detect_cycle]

Com: {fb}

Link: https://leetcode.com/problems/graph-valid-tree/#/description

Givennnodes labeled from0ton - 1and 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 = 5and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return 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.

Solution: Union Find

class Solution(object):
    def validTree(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: bool
        """
        if not n:
            return False

        parents = [-1 for _ in xrange(n)]
        num_of_sets = n
        for edge in edges:
            node1, node2 = edge
            node1_parent = self.find(parents, node1)
            node2_parent = self.find(parents, node2)

            if node1_parent == node2_parent:
                return False

            # make node1 and node2 pointing to the same parent.
            parents[node2_parent] = node1_parent
            num_of_sets -= 1

        return num_of_sets == 1

    def find(self, parents, curr_node):
        # base case
        if parents[curr_node] == -1:
            return curr_node

        return self.find(parents, parents[curr_node])

Revelation:

• If we can detect there exist cycle in this undirected graph or if finally we can not union all nodes into one set, the graph is not a valid tree.
• Using union_find, if the edge (node1<=>node2), node1 and node2 have been union into one set before this iteration, which means before we this edge, there exists a path which can make node1 connect to node2, now we get another edge connecting node1 and node2, which means there exist the cycle in this undirected graph, which means this graph is not a valid tree.
• Topological Sort can be used to detect the cycle for a directed graph, Union Find can be used to detect the cycle for an undirected graph.

Note:

• Time complexity = O(len(edges) * n), the time complexity of find = O(n), because here we didn't use 'union by rank' and 'path compression', the worst case for operation 'find' is O(n), think the tree like a list, 1->2->3->4->5 if find want to find its true parent, it will take O(n) time.
• Space complexity = O(n).