Leetcode 2685. Count the Number of Complete Components

Jimmy   Mar 22, 2025   536 words   ~15 mins
#Depth-First Search #Breadth-First Search #Union Find #Graph

Table of Contents

題目資訊

題目敘述

你被給予一個整數 $n$。有一個無向圖，其包含 $n$ 個頂點，編號從 $0$ 到 $n - 1$。你被給予一個二維整數數組 edges，其中 $edges[i] = [a_i, b_i]$ 表示存在一條連接頂點 $a_i$ 和 $b_i$ 的無向邊。

返回圖中完全連通組件的數量。

連通組件是圖的一個子圖，其中存在一條路徑可以連接任何兩個頂點，並且該子圖的頂點與子圖外的頂點之間沒有邊相連。

如果一個連通組件中的每一對頂點之間都存在一條邊，則稱該連通組件是完全的。

範例 1:

輸入: n = 6, edges = [[0,1],[0,2],[1,2],[3,4]]
輸出: 3
解釋: 從上圖可以看到，這張圖的所有組件都是完全的。

範例 2:

輸入: n = 6, edges = [[0,1],[0,2],[1,2],[3,4],[3,5]]
輸出: 1
解釋: 包含頂點 0、1 和 2 的組件是完全的，因為每對頂點之間都存在一條邊。另一方面，包含頂點 3、4 和 5 的組件不是完全的，因為頂點 4 和 5 之間沒有邊。因此，這張圖中完全的組件數量是 1。

約束條件:

  • $1 \leq n \leq 50$
  • $0 \leq edges.length \leq n \times (n - 1) / 2$
  • $edges[i].length == 2$
  • $0 \leq a_i, b_i \leq n - 1$
  • $a_i \neq b_i$
  • 沒有重複的邊。

直覺

此問題要求識別無向圖中完整連通分量的數量。完整連通分量是指在其子圖中，每一對不同的頂點都有一條唯一的邊連接，形成一個團（clique）。首先，我們需要確定圖中的連通分量，然後驗證每個連通分量是否構成一個完整的子圖。

解法

為了解決這個問題，我們採用聯合集合資料結構，也稱為不相交集合（Disjoint Set Union, DSU），該資料結構能夠高效地處理需要將頂點分組為連通分量的連和查找操作。

  1. 初始化:

    • 建立三個陣列：group，edgeCount，和 nodeCount。
      • group[i] 代表節點 i 所屬的組的領導者或 “父節點”。
      • edgeCount[i] 存儲以 i 為領導者的連通分量中的邊的數量。
      • nodeCount[i] 跟蹤以 i 為領導者的連通分量中的節點數量。

  2. 設定:

    • 初始化每個節點為其獨立的組：group[i] = i。
    • 初始化 edgeCount[i] = 0 對於所有 i。
    • 初始化 nodeCount[i] = 1 對於所有 i，因為每個節點最初都是自己的組件。

  3. 聯合集合操作:

    • 對於每條邊 [a_i, b_i]，進行聯合操作將連接的節點分組。
    • 使用 findGroup 函數進行路徑壓縮以找到每個節點的根，提高效率。
    • 在 unionGroup 中，如果兩個節點 i 和 j 屬於不同的組，將它們合併在一個領導者下，並合併它們的邊計數和節點計數。
    • 由於在節點之間增加了一條邊，因此每次聯合操作都增加邊計數。

  4. 路徑壓縮:

    • 對所有節點，應用 findGroup 將每個節點直接指向其根領導者，以避免關於組件連通性的重複檢查。

  5. 分量計算與驗證:

    • 去除 group 陣列中的重複項以找到所有唯一的連通分量。
    • 對於每個獨特的組件，通過檢查公式來驗證其是否完整：$\text{nodeCount}[el] \times (\text{nodeCount}[el] - 1) / 2 = \text{edgeCount}[el]$。如果為真，則表示為一個完整的子圖。

  6. 返回計數:

    • 返回完整連通分量的數量，也就是滿足由公式規定的完整性條件的組的數量。

此方法有效地確定圖中的所有連通分量，並利用組合邏輯判斷它們是否構成完整的子圖，充分利用聯合集合的能力進行高效的連通性檢查。

程式碼

C++

class Solution {
public:
    // 找出 'i' 所屬群組的根
    int findGroup(vector<int>& group, int i) {
        if (group[i] == i) 
            return i;
        else
            // 路徑壓縮以提高效率
            return group[i] = findGroup(group, group[i]);
    }

    // 將 i 和 j 所標識的兩個群組合併
    void unionGroup(vector<int>& group, vector<int>& edgeCount, vector<int>& nodeCount, int i, int j) {
        int groupI = findGroup(group, i);
        int groupJ = findGroup(group, j);

        // 如果它們屬於不同群組，合併它們
        if (groupI != groupJ) {
            group[groupJ] = groupI;
            edgeCount[groupI] += edgeCount[groupJ];
            nodeCount[groupI] += nodeCount[groupJ];
        }
        // 對合併的群組增加邊的計數
        edgeCount[groupI]++;
    }

    // 計算完整連通分量的數量
    int countCompleteComponents(int n, vector<vector<int>>& edges) {
        vector<int> group(n), edgeCount(n, 0), nodeCount(n, 1);

        // 初始化每個節點為自己的群組
        for (int i = 0; i < n; i++) 
            group[i] = i;

        // 每一條邊進行合併操作
        for (vector<int>& edge : edges) 
            unionGroup(group, edgeCount, nodeCount, edge[0], edge[1]);

        // 確保所有節點直接指向它們的根群組（壓縮路徑）
        for (int i = 0; i < n; i++) 
            findGroup(group, i);

        // 移除重複群組以計算唯一群組
        sort(group.begin(), group.end());
        auto lastUnique = unique(group.begin(), group.end());
        group.erase(lastUnique, group.end());

        int completeComponentsCount = 0;
        // 檢查每個群組是否形成完整的分量
        for (int el : group) {
            // 一個分量是完整的若它具有完整的邊數
            if (nodeCount[el] * (nodeCount[el] - 1) / 2 == edgeCount[el]) 
                completeComponentsCount++;
        }

        return completeComponentsCount;
    }
};

Python

class Solution:
    # 找到節點 'i' 所屬群組的根
    def findGroup(self, group, i):
        if group[i] == i:
            return i
        else:
            # 路徑壓縮以提高效率
            group[i] = self.findGroup(group, group[i])
            return group[i]

    # 合併由 i 和 j 標識的兩個群組
    def unionGroup(self, group, edgeCount, nodeCount, i, j):
        groupI = self.findGroup(group, i)
        groupJ = self.findGroup(group, j)

        # 如果它們屬於不同的群組，則合併它們
        if groupI != groupJ:
            group[groupJ] = groupI
            edgeCount[groupI] += edgeCount[groupJ]
            nodeCount[groupI] += nodeCount[groupJ]
        # 增加合併後群組的邊的計數
        edgeCount[groupI] += 1

    # 計算完整連通元件的數量
    def countCompleteComponents(self, n, edges):
        group = list(range(n))
        edgeCount = [0] * n
        nodeCount = [1] * n

        # 初始化每個節點為其自身群組
        for i in range(n):
            group[i] = i

        # 為每條邊進行合併操作
        for edge in edges:
            self.unionGroup(group, edgeCount, nodeCount, edge[0], edge[1])

        # 確保所有節點直接指向其根群組（壓縮路徑）
        for i in range(n):
            self.findGroup(group, i)

        # 去除重複以計算唯一群組
        group.sort()
        group = list(dict.fromkeys(group))

        completeComponentsCount = 0
        # 檢查每個群組是否形成完整元件
        for el in group:
            # 如果一個元件擁有完整的邊組合，則認為它是完整的
            if nodeCount[el] * (nodeCount[el] - 1) // 2 == edgeCount[el]:
                completeComponentsCount += 1

        return completeComponentsCount

複雜度分析

  • 時間複雜度: 演算法由多個不同的階段組成，這些階段共同決定了時間複雜度。首先，初始化 group、edgeCount 和 nodeCount 陣列各需要 $O(n)$。由於路徑壓縮和按秩合併的優化，邊的合併操作總共需要 $O(n)$。路徑壓縮迴圈確保每個節點指向正確的代表，這也需要 $O(n)$。排序 group 陣列需要 $O(n \log n)$。最後，掃描群組以計算完整組件需要 $O(n)$。因此，整體時間複雜度由於排序 group 陣列而為 $O(n \log n)$。

  • 空間複雜度: 空間複雜度由 group、edgeCount 和 nodeCount 陣列決定，每個陣列需要 $O(n)$ 的空間。因此，空間複雜度為 $O(n)$。

Disclaimer: All reference materials on this website are sourced from the internet and are intended for learning purposes only. If you believe any content infringes upon your rights, please contact me at csnote.cc@gmail.com, and I will remove the relevant content promptly.


Feedback Welcome: If you notice any errors or areas for improvement in the articles, I warmly welcome your feedback and corrections. Your input will help this blog provide better learning resources. This is an ongoing process of learning and improvement, and your suggestions are valuable to me. You can reach me at csnote.cc@gmail.com.