LeetCode 解題筆記：2685. Count the Number of Complete Components

作者：王一哲
日期：2026年7月11日


LeetCode 題目連結：2685. Count the Number of Complete Components

解題想法

中等難度題。題目給一張無向圖，節點數量 $n$，邊的資料 $edges$，要找出圖中之有幾個子圖是完全連接的，也就是子圖中任意兩個節點之間有一條邊。我是用併查集處理這題，併查集之中同一個連通區塊就是一張子圖，為了檢查子圖是否完全連接，除了區塊中節點的數量 $sz$ 以外，還需要儲存區塊中邊的數量 $edge$。最後再寫一個自訂函式 find_ans，檢查節點 $i = 0$ 到 $i = n-1$，如果 $i$ 是這個區塊的根節點，再檢查區塊中節點數量 $m$ 與邊的數量 $e$ 是否符合 $$ e = \frac{m \times (m-1)}{2} $$ 如果符合就將答案 $ans$ 加 1，最後再回傳 $ans$。

Python 程式碼

Runtime: 46 ms, beats 49.53%. Memory: 19.78 MB, beats 71.89%.

class DisjointSetUnion:
    def __init__(self, n):
        self.n = n
        self.parent = list(range(n))
        self.sz = [1] * n  # 同一個連通區塊中有幾個節點
        self.edge = [0] * n  # 同一個連通區塊中有幾條邊
    
    def rfind(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.rfind(self.parent[x])
        return self.parent[x]
    
    def unite(self, u, v):
        root_u, root_v = self.rfind(u), self.rfind(v)
        if root_u != root_v:
            if self.sz[root_u] < self.sz[root_v]:
                root_u, root_v = root_v, root_u
            self.sz[root_u] += self.sz[root_v]
            self.edge[root_u] += self.edge[root_v] + 1
            self.parent[root_v] = root_u
            return True
        else:
            self.edge[root_u] += 1  # 多一條新的邊
            return False
    
    def find_ans(self):
        ans = 0  # 答案
        # 檢查所有節點所在的區塊是否完全連接
        for i in range(self.n):
            if self.parent[i] == i:  # 只從區塊根節點開始檢查
                m = self.sz[i]  # 區塊中的節點數量
                e = self.edge[i]  # 邊的數量
                if e == m * (m-1) // 2:  # 所有的節點之間都有邊
                    ans += 1
        return ans            

class Solution:
    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:
        # 建立併查集物件
        dsu = DisjointSetUnion(n)
        # 連接所有的邊
        for u, v in edges:
            dsu.unite(u, v)
        # 檢查所有節點所在的區塊是否完全連接
        return dsu.find_ans()

C++ 程式碼

Runtime: 39 ms, beats 71.93％. Memory: 121.14 MB, beats 89.87%.

class DisjointSetUnion {
private:
    int n;
    vector<int> parent, sz, edge;

public:
    DisjointSetUnion(int x) {
        n = x;
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
        sz.assign(n, 1);
        edge.assign(n, 0);
    }
    
    int rfind(int x) {
        if (parent[x] == x) return x;
        parent[x] = rfind(parent[x]);
        return parent[x];
    }
    
    bool unite(int u, int v) {
        int root_u = rfind(u), root_v = rfind(v);
        if (root_u != root_v) {
            if (sz[root_u] < sz[root_v]) {
                swap(root_u, root_v);
            }
            sz[root_u] += sz[root_v];
            edge[root_u] += edge[root_v] + 1;
            parent[root_v] = root_u;
            return true;
        } else {
            edge[root_u]++;
            return false;
        }
    }
    
    int find_ans() {
        int ans = 0;
        for(int i = 0; i < n; i++) {
            if (parent[i] == i) {
                int m = sz[i], e = edge[i];
                if (e == m * (m-1) / 2) ans++;
            }
        }
        return ans;
    }
};

class Solution {
public:
    int countCompleteComponents(int n, vector<vector<int>>& edges) {
        DisjointSetUnion dsu(n);
        for(auto it : edges) {
            dsu.unite(it[0], it[1]);
        }
        return dsu.find_ans();
    }
};