# LeetCode 261. Graph Valid Tree

## Description

https://leetcode.com/problems/minimum-size-subarray-sum/

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:

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

Example 2:

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

Constraints:

• `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.

## Explanation

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.

## Python Solution

``````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).