leetcode-union-find

685. Redundant Connection II.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 u.
        """
        while u != self._parents[u]:
            # pass compression technique: make x and all parents of x pointed to root node of x so that we don’t have to traverse all intermediate nodes again.(flat tree) 
            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:
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        """
        Thought process:
        
        1. Goal is to find the one additional edge, if we removed it, making the directed graph become a rooted tree.
        
        2.A rooted tree is except root node, every node in the graph has only one parent node. So, we need to make sure there's no duplicated parent happening on a certain node after removing the edge.
        So, 
            step1: to find node with duplicated parents(it's imppossible to have more than 3 duplicated parent in our problem because only one addition edge that we need to remove)
        
        
        """
        n = len(edges)
        # 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-1, b-1):
                # there's cycle when union return False
                return [a, b] 
            
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        """
        Thought process:
        
        1. Goal find the one additional edge, if we removed it, making the directed graph become a rooted tree.
        
        2.A rooted tree is except root node, every node in the graph has only one parent node. So, we need to make sure there's no duplicated parent happening on a certain node after removing the edge.
        
        So  
            step1: to determin if there's a node with duplicated parenet
            
                step1-1: 
                    If yes, to find two edges linked to the node called cand1 and cand2(it's imppossible to have more than 2 edges linked to the node in our problem because only one addition edge that we need to remove)
                    Otherwise, we assign two edges(cand1, cand2) as None
            step2: to determin is there's a cycle in directed graph using union find
                step2-1:
                    If it's acyclic, return cand2(the last edge linked to node with duplicated paretn)
                    if it's cyclic:
                        and if there's not a node duplicated parent:
                            return current edge making it cyclic( which make the directed graph not a root tree)
                        and if it has node with dupicated paretn:
                            return cand1(have to remove the one inside the cycle)
                    
        T: O(n) + O(1*) = O(n)
        S: O(n)
        """
        # step1: find if a decendant node has the duplicated parent 
        cand1, cand2, parent = None, None, {} #{decendant:parent}
        for a, b in edges:
            # find
            if b in parent: 
                # node a has two parents
                cand1, cand2 = [parent[b], b], [a, b]
                break
            parent[b] = a
            
        n = len(edges)
        # step2: 
        unionFind = UnionFindSet(n)
        for node1, node2 in edges:
            # tricky prart
            if [node1, node2] == cand2: 
                continue
            # using union-find to check if node1 and node b connected already
            if not unionFind.union(node1 - 1, node2 - 1):
                # no noded has duplicated parent -> detect cycle in undirected graph using union-find
                if cand1 == cand2 == None:
                    return [node1, node2] # return the edge making directec graph cyclic
                if cand1: 
                    # if there's a component in directed graph, cand1 must be the one we need to remove becasue we skip the cand2 when build union-find
                    return cand1
        # nothing happen so far, return the second edge linked to the node having duplicated parent node becasue we skip the cand2 when build union-find
        return cand2