0323-number-of-connected-components-in-an-undirected-graph¶

class unionFind:
    def __init__(self,n):  # [[2,3],[1,2],[1,3]]
        self.n = n
        self.parent = [i  for i in range(n)] # [0 1 2 3]
        self.size = [1] * n
    #
    def union(self, a, b): #  1 2
        root_a = self.find(a)  # 1
        root_b = self.find(b) # 2
        
        if root_a == root_b:
            return 0
        elif  self.size [root_a] <  self.size[root_b]:
            self.parent[root_b] = root_a #  [0 1 1 2]
            self.size [root_a] += 1
        else:
            self.parent[root_a] = root_b
            self.size [root_b] += 1
        return 1
    def find(self, a): # 0
        if a == self.parent[a]:
            return a
        return self.find(self.parent[a])
    def num_of_componenets(self):
        return len(set(self.parent))

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        #  n = 5, edges = [[0,1],[1,2],[3,4]]
        # 0 -> 1 -> 2   
        #   3 -> 4
        #  2
        # 
        # uf ->  n
        #     parent = [n]
        #     
        #     union a ,b  
        #      find root of a and b
        #      set root of a as b
        #     find -> a
        #        iterate until parent = a
        #        a
        #     num_of_componenets -> count number of unique parents
        #
        # edges -> edge uf.union 
        # num_of_componenets return
        #  [[0,1],[1,2],[3,4]]
        #   [0 1 2 3 4]
        #   0,1 -> [0 0 2 3 4]
        #   1,2  -> []
        #
        # edge cASE [[2,3],[1,2],[1,3]]
        # 1->   2 -> 3 -> 1   0
        #              

        uf = unionFind(n)
        cnt = n
        for a,b in edges: # [[0,1],[1,2],[3,4]]
            cnt -= uf.union(a,b)

        return cnt