[LeetCode] Graph Valid Tree

leetcode

By definition, we know that “tree” is a acyclic, connected graph.
Therefore, in this problem, we only need to check if it’s acyclic and connected.

The basic idea is, if there’s a node that we’ve visited and it’s not the parent of node, then there is cycle. We can also use Union Find to detect cycles in undirected graphs. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def validTree(self, n, edges):
    """
    :type n: int
    :type edges: List[List[int]]
    :rtype: bool
    """
    # check cycle and connected
    from collections import defaultdict
    graph = defaultdict(list)
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    visit = set()

    def DFS(node, parent):
        if node in visit: return False
        visit.add(node)
        for neighbor in graph[node]:
            if neighbor not in visit:
                child = DFS(neighbor, node)
                if not child: return False
            else:
                if neighbor != parent:
                    return False
        return True
    cycle = DFS(0, -1)
    return cycle and len(visit) == n

There is also another way to check cycles – using Union Find.
The idea is, for each edge (u,v), u and v cannot be in the same set.
This is useful if the given input is edges instead of nodes because you don’t need to construct the nodes again. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def validTree(self, n, edges):
    # write your code here
    if n == 1: return True 
    
    def find(node):
        if graph[node] == node: return node
        root = find(graph[node])
        graph[node] = root # path compression
        return root
    
    def union(root, node):
        graph[graph[node]] = graph[root]
    
    graph = list(range(n))
    visit = set()
    for a, b in edges:
        visit.add(a)
        visit.add(b)
        if find(a) == find(b):
            return False 
        union(a, b)
    
    return len(visit) == n

Reference: geeksforgeeks