LC261. Graph Valid Tree

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        """  time O(E+V) space O(E+V)  
        1.build graph (adjacency list)
        2. iterative dfs (stack + map ) traversal => stack + parent hash map with {0:-1} initialization
        3. for each node, push its nei into stack and add into hash map, meanwhile remove node as neighbor's neighbor in graph 
        """
        if len(edges) != n-1:
            return False
        # build gragh 
        g = {}
        stack = [0]
        for n1,n2 in edges:
            if n1 not in g:
                g[n1] = []
            if n2 not in g:
                g[n2] = []
            g[n1].append(n2)
            g[n2].append(n1)
        parent = {0:-1} # root node has no parent 
        while stack:
            node = stack.pop()
            for nei in g.get(node,[]):  # need to consider 0 not in graph, to skip, otherwise it caused KeyError: 0
                # ignore cases where current node's parent node is the neighbor node
                if nei == parent[node]:
                    continue
                # there is cycle 
                if nei in parent:
                    return False 
                stack.append(nei)
                parent[nei] = node
        return n == len(parent) 

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        """ time O(N) space O(N)
        1.build graph (adjacency list)
        2. iterative dfs (stack + set ) traversal
        3. for each node, push its nei into stack and add into set, remove 
        """
        if len(edges) != n-1:
            return False
        # build gragh 
        g = [[]for _ in range(n)]
        stack = [0]
        seen = {0}
        for n1,n2 in edges:
            g[n1].append(n2)
            g[n2].append(n1)
        
        while stack:
            node = stack.pop()
            for nei in g[node]:
                if nei in seen:
                    continue 
                stack.append(nei)
                seen.add(nei)
        return n == len(seen) 

class UF:
    def __init__(self,n):
        self.parents = [i for i in range(n)]
        self.ranks = [1] * n
        self.cnt = n
    def find(self, u):
        if u != self.parents[u]:
            self.parents[u] = self.find(self.parents[u])
        return self.parents[u]

    def union(self,u,v):
        pu = self.find(u)
        pv = self.find(v)
        
        if pv == pu:
            return False
        self.cnt -= 1 
        if self.ranks[pu] < self.ranks[pv]: # note here is to update ranks of parent node insted of current node 
            self.ranks[v] += self.ranks[u]
            self.parents[u] = pv
            
        else:
            self.ranks[pu] += self.ranks[pv]
            self.parents[v] = pu
        return True 
    
class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        """ time O(N * alpha(N)) space O(V) ~O(N)
        0. initialize each vertice has itself as root 
        1. for each V pairs, find its root 
        2. if  root not same, union them; otherwise, there is a circle.
        3. after loop through all vertices, if size of uf > 1, tree is not valid 
        """
        if len(edges) != n-1:
            return False
        uf = UF(n)
        for e1,e2 in edges:
            if not uf.union(e1,e2):
                return False
        return uf.cnt == 1