題目描述: 給定 n 個節點的無向圖和一組邊,計算完全連通分量的數量。一個連通分量是「完全的」若其中每對節點之間都有邊相連。
解題思路: 先找出所有連通分量(使用 BFS/DFS 或 Union-Find)。對每個連通分量,檢查它是否是完全圖:一個有 v 個節點的完全圖恰好有 v*(v-1)/2 條邊。
因此,對每個連通分量,統計其節點數 v 和邊數 e,若 e == v*(v-1)/2 則為完全分量。
時間複雜度: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),適合稠密圖。