leetcode-graph

261. Graph Valid Tree.py

class UnionFindSet:
    def __init__(self, n):
        #Initially, all elements are single element subsets.
        self._parents = [node for node in range(n)]
        # it's like height of tree but it's not always equal to height because path compression technique.
        self._ranks = [1 for i in range(n)]
    
    def find(self, u):
        """
        The find method with path compression, return root of node x, whih can be found by following the chain that begins at x.
        Pass Compression technique:
            Make given node u and all parents of node u pointed to root node of u so that we don’t have to traverse all intermediate nodes again.(flat tree)
        """
        while u != self._parents[u]:
            # pass compression technique: make the found root as parent of x so that we don’t have to traverse all intermediate nodes again. 
            self._parents[u] = self._parents[self._parents[u]]
            u = self._parents[u]
        return u
    
    def union(self, u, v):
        """
        The union method, with optimization union by rank. It returns False if a u and v are in the same tree/connected already, True if otherwise.
        """
        root_u, root_v = self.find(u), self.find(v)
        if root_u == root_v: 
            return False
        
        if self._ranks[root_u] < self._ranks[root_v]:
            self._parents[root_u] = root_v
        elif self._ranks[root_u] > self._ranks[root_v]:
            self._parents[root_v] = root_u
        else:        
            # If ranks are same, then make one as root and increment its rank by one 
            self._parents[root_v] = root_u
            self._ranks[root_u] += 1
        return True
    
class Solution:
    """
    Problem Clarification:
        Given n nodes and edge list of undirected graph, to find whether the graph is a tree or not.
    
    Thought Process:
        What's definition of valid tree?
            A graph is a tree if and only if it’s connected and acyclic graph with n nodes and n-1 edges.
            
        DFS:
            Step1: convert edge list into adjacency list
            Step2: Traverse the graph using dfs. During traversal, if we found a node whose neighbor except parent node of current node is visted already, it's cyclic graph.
            Step3: To check if connected graph by checking wether all nodes of the graph are vistited already
                If not, unconnected graph. 
        BFS
            Step1: convert edge list into adjacency list
            Step2: Traverse the graph using bfs. During traversal, if we found a node whose neighbor except parent node of current node is visted already, it's cyclic graph.    
            Step3: To check if connected graph by checking wether all nodes of the graph are vistited already.
                If not, unconnected graph. 
            
        Union-Find
            Step1: check if it's n nodes and n-1 edges. If not return False
            Step2: We iterate each edge, for each step we merge node a to node b together by union method provided by union-find data structure. This steps takes O(m) because we can think of each union takes O(1).
                If the node a and node b is connected already, then there must be a cycle --> return False
            Step3. After finished all the edges, wihtout returning False. It mean it's connected and acyclic graph                  --> return True.

    Time complexity Analysis:
        DFS:
            step1: takes O(n+m)
            T:O(n+m), n is number of nodes and m is number of edges
        BFS:
            T:O(n+m), n is number of nodes and m is number of edges
    n = 5, and edges = [[0,1], [0,2], [0,3], [1,4]]
    0 -1 -4
    | \ 
    2  3
    """
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        """
        DFS
        T:O(n+m)
        S:O(n+m) adjacent list has n nodes in dict, but inner list of each nodes add to a total of m. So, it's O(n+m)
        """
        m = len(edges)
        if m != n-1:
            return False
        # step1:
        g = collections.defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        # step2:
        self.visited = [False for _ in range(n)]
        if self.dfs(cur_node=0, parent=-1, visited=self.visited, g=g):
            # found cycle
            return False
        # step3:
        if sum(self.visited) != n:
            # it's unconnected graph
            return False
        return True
    
    def dfs(self,cur_node, parent, visited, g):
        """to detect if undirected graph is cyclic"""
        visited[cur_node] = True
        # like n-arr tree
        for nei_node in g[cur_node]:
            if not visited[nei_node]:
                self.dfs(nei_node, cur_node, visited, g)
            elif visited[nei_node] and nei_node!=parent:
                return True
            else:
                continue
        return False
        
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        """
        BFS
        T:O(n+m)
        S:O(n+m)[adjacency list] + O(n) [queue]. In worst case, we put n nodes in the queue.
        """
        m = len(edges)
        if m != n-1:
            return False
        # step1: 
        g = collections.defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        # step2:
        visited = [False for _ in range(n)]
        visited[0]=True
        q = collections.deque([(0, -1)]) # [(starting_node, parent_node)]
        while q:
            cur_node, parent = q.popleft()
            for nei_node in g[cur_node]:
                if visited[nei_node] and nei_node!=parent:
                    return False
                if visited[nei_node] and nei_node==parent:
                    continue
                visited[nei_node] = True
                q.append((nei_node, cur_node))
        # step3:
        if sum(visited) != n:
            # it's unconnected graph
            return False
        return True
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        """
        Union-Find
        T: O(m) because we iterate each edge and for each each merge could be consider as O(1)
        S: O(n) because of union-find data sturcture
        """
        if len(edges) != n - 1: 
            return False
        # create a new UnionFind object with n nodes. 
        unionFind = UnionFindSet(n)
        # for each edge, check if a merge happened, because if it didn't, there must be a cycle.
        for a, b in edges: 
            if not unionFind.union(a, b):
                # there's cycle when union return False
                return False
        # If we got this far, there's no cycles!
        return True