MediumRating 1769

2685. Count the Number of Complete Components

depth-first-searchbreadth-first-searchunion-findgraph

在 LeetCode 上作答 ↗

解題說明

Count the Number of Complete Components

題目描述：給定 n 個節點的無向圖和一組邊，計算完全連通分量的數量。一個連通分量是「完全的」若其中每對節點之間都有邊相連。

解題思路：先找出所有連通分量（使用 BFS/DFS 或 Union-Find）。對每個連通分量，檢查它是否是完全圖：一個有 v 個節點的完全圖恰好有 v*(v-1)/2 條邊。

因此，對每個連通分量，統計其節點數 v 和邊數 e，若 e == v*(v-1)/2 則為完全分量。

C++ 解法

複雜度分析

時間複雜度：O(V + E) — BFS 遍歷所有節點和邊各一次

空間複雜度：O(V + E) — 鄰接表和 visited 陣列

虛擬碼

1. Build adjacency list
2. For each unvisited node, BFS to find its connected component:
   a. Count vertices (v) and edges (e) in the component
   b. Each edge is counted twice in adjacency list, so actual edges = e / 2
3. If actual edges == v * (v-1) / 2, this is a complete component
4. Return total count of complete components

其他解法

Union-Find + 度數檢查法：用並查集分組，記錄每組的節點數和邊數。完全圖中每個節點的度數為 v-1，所以也可以檢查分量內所有節點的度數是否相同且等於 v-1。
鄰接矩陣法：對小規模圖使用鄰接矩陣。完全分量檢查變成矩陣子區塊是否全為 1（對角線除外）。空間 O(V^2)，適合稠密圖。

延伸思考

如果要找出最大的完全連通分量（節點最多的），如何修改？
如果要在動態圖中（邊不斷新增）即時統計完全分量數，如何設計？
如果定義「幾乎完全分量」為缺少最多 k 條邊的分量，如何計數？

Count the Number of Complete Components — CaffeCode