323. Connected Component in Undirected Graph.md

323. Connected Component in Undirected Graph

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

solution

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

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        graph = [[] for _ in range(n)]
        visited = set()
        ans = 0

        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        def bfs(node: int, seen: set[int]) -> None:
            q = collections.deque([node])
            seen.add(node)

            while q:
                u = q.pop()
                for v in graph[u]:
                  if v not in seen:
                    q.append(v)
                    seen.add(v)

        for i in range(n):
            if i not in visited:
                bfs(i, visited)
                ans += 1
        return ans

时间复杂度：O(V+E)
空间复杂度：O(V+E)

• 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))