Graph Valid Tree — LC Medium

261. Graph Valid Tree

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 <= n <= 2000
• 0 <= edges.length <= 5000
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• There are no self-loops or repeated edges.

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        
        # [0,1,2,3,4] ==> n = 5
        # edges: [[0,1],[0,2],[0,3],[1,4]]
        # connect 0, 1
        # root of 0 is 0
        # root of 1 is 1
        # since they are different, it becomes
        # [0,0,2,3,4]
        
        # connect 0, 2
        # root[0] is 0, root[2] is 2
        # since they are different, it becomes
        # [0,0,0,3,4]
        
        # connect 0, 3
        # root[0] is 0, root[3] is 3
        # since they are different, it becomes
        # [0,0,0,0,4]
        
        # connect 1, 4
        # root[1] is 0, root[4] is 4
        # since they are different, it becomes
        # [0,0,0,0,0]
        
        
        # [0,1,2,3,4] ==> n = 5
        # edges: [[0,1],[1,2],[2,3],[1,3],[1,4]]
        
        # connect 0, 1
        # root[0] is 0, root[1] is 1
        # since they are different, it becomes
        # [0,0,2,3,4]
        
        # connect 1, 2
        # root[1] is 0, root[2] is 2
        # since they are different, it becomes
        # [0,0,0,3,4]
        
        # connect 2, 3
        # root[2] is 2, root[3] is 3
        # [0,0,0,0,4]
        
        # connect 1, 3
        # root[1] is 0, root[3] is 0
        # they are same. then it means that they share the same root, if they try to connect, it makes cycle. return False
        
        if len(edges) != n - 1:
            return False
        
        self.root = [i for i in range(n)]
        
        for vertex1, vertex2 in edges:
            
            if not self.union(vertex1, vertex2):
                return False
            
        return True
    
    def findRoot(self, target: int) -> int:
        while target != self.root[target]:
            target = self.root[target]
        return target
    
    def union(self, vertex1: int, vertex2: int) -> None:
        root1 = self.findRoot(vertex1)
        root2 = self.findRoot(vertex2)
        if root1 == root2:
            return False
        
        self.root[root2] = root1
        
        return True