⚡Flashcard Drill➔
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

  1. Group the vertices into components with union-find.
  2. Count the vertices and the edges per component.
  3. A component with k vertices is complete exactly when it has k * (k - 1) / 2 edges.
  4. 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 == 0 edges, 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems