Problem description:

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

Example 1:

https://assets.leetcode.com/uploads/2021/03/12/tree1-graph.jpg

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

Example 2:

https://assets.leetcode.com/uploads/2021/03/12/tree2-graph.jpg

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

Solution:

If a graph does not have loop, number of edges would be number_of_vertex-1

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n-1:
            return False
        
        graph = defaultdict(list)
        for edge in edges:
            graph[edge[0]].append(edge[1])
            graph[edge[1]].append(edge[0])
        visited = set([])
        def dfs(node):
            visited.add(node)
            for n in graph[node]:
                if n not in visited:
                    dfs(n)
        dfs(0)
        return len(visited) == n

Union Find

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        def find(i, vertex):
            if i == vertex[i]:
                return i
            else:
                return find(vertex[i], vertex)
        # union find to check if cycle exist
        vertex = [i for i in range(n)]
        for edge in edges:
            u, v = edge[0], edge[1]
            parent_u, parent_v = find(u, vertex), find(v, vertex)
            if parent_u == parent_v:
                return False
            else:
                vertex[parent_u] = parent_v
        return len(edges) == n-1

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        queue = deque([0])
        visited = set()
        # use set to keep all neighbors
        graph = defaultdict(set)
        for edge in edges:
            graph[edge[0]].add(edge[1])
            graph[edge[1]].add(edge[0])
        
        while queue:
            front = queue.popleft()
            visited.add(front)
            for neighbor in graph[front]:
                if neighbor in visited:
                    return False
                visited.add(neighbor)
                queue.append(neighbor)
                # remove this edge from neighbor
                graph[neighbor].remove(front)
        return len(visited) == n

time complexity: $O(V+E)$
space complexity: $O()$
reference:
related problem: