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