You have a graph of
n nodes labeled from
n - 1. You are given an integer n and a list of
edges[i] = [ai, bi] indicates that there is an undirected edge between nodes
bi in the graph.
true if the edges of the given graph make up a valid tree, and
Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] Output: true
Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]] Output: false
1 <= 2000 <= n
0 <= edges.length <= 5000
edges[i].length == 2
0 <= ai, bi < n
ai != bi
- There are no self-loops or repeated edges.
Use the union-find to group nodes. If the graph is a tree, it should have only one connected component and also the number of nodes – 1 should be equal to the number of edges.
class Solution: def validTree(self, n: int, edges: List[List[int]]) -> bool: if n - 1 != len(edges): return False self.father = [i for i in range(n)] self.size = n for a, b in edges: self.union(a, b) return self.size == 1 def union(self, a, b): root_a = self.find(a) root_b = self.find(b) if root_a != root_b: self.size -= 1 self.father[root_a] = root_b def find(self, node): path =  while node != self.father[node]: path.append(node) node = self.father[node] for n in path: self.father[n] = node return node
- Time Complexity: O(N).
- Space Complexity: O(N).