日期：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()
