*323. Connected Component in Undirected Graph

https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/

solution

• bfs: 模版计算无向图的独立部分

时间复杂度：O() 空间复杂度：O()

• dfs

• union find

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        def find(node):
            if parent[node] != node:
                parent[node] = find(parent[node])
            return parent[node]

        parent = list(range(n))
        for a, b in edges:
            parent[find(a)] = find(b)

        return sum(i == find(i) for i in range(n))