NeetCode #596LC-2685MediumGraphs
← Back to All Problems#596 · #2685 · Count the Number of Complete Components(统计完全连通分量的数量)
📌 Problem Statement & Constraints
You are given an undirected graph with
n vertices and edges. A connected component is complete if every pair of its vertices has an edge. Return the number of complete connected components. Constraints: 1 <= n <= 50, 0 <= edges.length <= n * (n - 1) / 2.💡 Core Algorithmic Approaches
- Group the vertices into components with union-find.
- Count the vertices and the edges per component.
- A component with
kvertices is complete exactly when it hask * (k - 1) / 2edges. - Note that the edges within a component are exactly the input edges whose endpoints share a root.
💻 Benchmark Python3 Implementation
class Solution:
def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:
from collections import defaultdict
parent = list(range(n))
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for a, b in edges:
ra, rb = find(a), find(b)
if ra != rb:
parent[ra] = rb
nodes = defaultdict(int)
for i in range(n):
nodes[find(i)] += 1
edge_cnt = defaultdict(int)
for a, b in edges:
edge_cnt[find(a)] += 1 # both endpoints share the component
res = 0
for root, cnt in nodes.items():
if edge_cnt[root] == cnt * (cnt - 1) // 2: # complete graph
res += 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(V + E * alpha(V)): effectively linear.
💾 Space Complexity
O(V) for the maps.
⚠️ Interview Pitfalls & Follow-ups
- Counting edges by iterating all pairs: O(V^2); counting input edges is O(E).
- Forgetting that a single-vertex component is complete:
0 == 0edges, so it counts -- correctly. - Using
find(a)after unions change roots: the find calls at the end resolve to the final roots. - Confusing complete with connected: completeness requires all pairs to be adjacent.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.