323. Number of Connected Components in an Undirected Graph

Question: Number of Connected Components in an Undirected Graph

Solution

想法：Connection 的話就是 Union & Find

可以參考 684. Redundant Connection 題，概念一樣

最後計算 group 的時候，題目給定 n 個 node，所以一開始一定是 n 個 group，每一次成功 union node1 & node2，就將 n 減 1。

Time Complexity: O(edges + n)

class Solution:
    def countComponentsS(self, n: int, edges: list[list[int]]) -> int:
        parent = [i for i in range(n)]
        rank = [1] * n
        def find_parent(node):
            p = parent[node]
            while p != parent[p]:
                parent[node] = parent[p]
                p = parent[parent[p]]
            return p
        def union(n1, n2):
            p1, p2 = find_parent(n1), find_parent(n2)
            if p1 == p2:
                return 0 
            elif rank[p1] >= rank[p2]:
                parent[p2] = p1
                rank[p1] += rank[p2]
            else:
                parent[p1] = p2
                rank[p2] += rank[p1]
            return 1
        res = n
        for n1, n2 in edges:
            n -= union(n1, n2)
        return res

Video Solution