Leetcode 261: Graph Valid Tree

https://leetcode.com/problems/graph-valid-tree/

Graph Valid Tree

Total Accepted: 2794 Total Submissions: 10778 Difficulty: Medium

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? Show More Hint

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 inedges.

Overall idea

We need to check two properties to determine whether a set of edges form a valid tree:

it has n-1 edges
it is acyclic

Code 1 (Union Find)

class Solution(object):
    def validTree(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: bool
        """
        union_arr = range(n)
        def find_union(p):
            if  union_arr[p] == p:
                return p
            else:
                return find_union(union_arr[p])        
                
        for p1, p2 in edges:
            p1_set = find_union(p1)        
            p2_set = find_union(p2)
            if p1_set == p2_set:
                return False
            union_arr[p1_set] = p2_set
        
        return len(edges) == n-1

Idea

This algorithm uses an idea called union find. You first initialize each node so that each node itself forms a node set. (We use `union_arr` to record which set a node belongs to). As we traverse all edges, we will find connected components. The union find algorithm makes sure that every node in a connected component will point to a same node set by using `find_union` function. Therefore, if we see a new edge with two points in the same node set, we will return False because the edge makes a cycle in the graph. If no cycle is found, we will finally check if there are exactly `n-1` edges to form a tree rather than disjoint parts in the graph. (line 22)

Reference

https://leetcode.com/discuss/52563/ac-java-union-find-solution

http://www.geeksforgeeks.org/union-find/

Updated 2016/09/30:

The union find algorithm can also be used to find connected components in an undirected graph. See leetcode 130: Surrounding Regions.

Code 2 (DFS)

class Solution(object):
    def validTree(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: bool
        """
        adj = {s:[] for s in range(n)}
        for p1, p2 in edges:
            adj[p1] += [p2]
            adj[p2] += [p1]
        stk = [0]
        while stk:
            cur = stk.pop()
            stk.extend(adj.pop(cur, []))
        return len(edges)==n-1 and not adj

Idea

We start to visit all nodes from node 0. (line 12) If we finish traversing all reachable nodes but there are still some adjacency matrix entry left then we know the given edges actually form multiple separate graphs. Therefore we should return False.

Code 3(BFS)

from collections import deque
class Solution(object):
    def validTree(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: bool
        """
        adj = {s:[] for s in range(n)}
        for p1, p2 in edges:
            adj[p1] += [p2]
            adj[p2] += [p1]
        q = deque()
        q.append(0)
        while q:
            cur = q.popleft()
            q.extend(adj.pop(cur, []))
        return len(edges)==n-1 and not adj

Idea

Similar idea as in code 2. But you implement the traversal of nodes using `deque`.

Leetcode 261: Graph Valid Tree

Graph Valid Tree

Leave a comment

Cancel reply