Napman's Notes

Count the Number of Complete Components

Properties1
tagsreview/leetcode

3 min read

2685. Count the Number of Complete Components

Difficulty: Medium | Date: 2026-07-11

Patterns: Union Find | Graphs Data Structures: Array

Problem

Given an undirected graph with n nodes and a list of edges, count how many connected components are “complete” - meaning every pair of nodes in the component is directly connected by an edge.

My Approach

Recognized the graph could have multiple components so reached for Union Find to group them. For each component, wanted to verify it was fully connected. Initially thought about checking each node’s degree (n-1 edges per node), but realized a cleaner check exists at the component level.

Key Insight

A complete component with n nodes must have exactly n*(n-1)/2 edges. Track node count and edge count per component root in the Union Find. At the end, check if edge_count == node_count * (node_count - 1) // 2 for each root.

Why n(n-1)/2:* Each node shakes hands with every other node - that’s n-1 handshakes per node. Multiply across all n nodes: n*(n-1). But each handshake involves 2 people, so every handshake is counted twice. Divide by 2.

Solution

from collections import defaultdict
 
class UnionFind:
    def __init__(self, n):
        self.root = {}
        self.edge_count = defaultdict(int)
        self.node_count = defaultdict(int)
        for node in range(n):
            self.root[node] = node
            self.node_count[node] = 1
 
    def find(self, node):
        if self.root[node] != node:
            self.root[node] = self.find(self.root[node])
        return self.root[node]
 
    def union(self, a, b):
        root_a, root_b = self.find(a), self.find(b)
        if root_a == root_b:
            self.edge_count[root_a] += 1
            return
        self.root[root_b] = root_a
        self.node_count[root_a] += self.node_count[root_b]
        self.edge_count[root_a] += self.edge_count[root_b] + 1
 
 
class Solution:
    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:
        uf = UnionFind(n)
        for u, v in edges:
            uf.union(u, v)
 
        ans = 0
        for node in range(n):
            root = uf.root[node]
            edge_cnt = uf.edge_count[root]
            nodes = uf.node_count[root]
            if node == root and edge_cnt == (nodes * (nodes - 1)) // 2:
                ans += 1
        return ans

Complexity

  • Time: O(n + E) - O(n) to initialize + O(E * α(n)) to process edges + O(n) final loop
  • Space: O(n) - root, node_count, edge_count all indexed by node

Prerequisites

Review Log

  • 2026-07-11 [Good] - fuzzy: n*(n-1)/2 formula (kept dropping the n), edge count merging when combining two components; clicked: Union Find approach, per-root node/edge tracking, same-component edge handling
  • 2026-07-18 [Good] - fuzzy: completeness formula (cycled through wrong guesses before n*(n-1)//2), why node==root check is needed; clicked: Union Find approach, per-root tracking, same-component edge handling
  • 2026-07-25 [Good] - fuzzy: same-component edge counting (needed hint that returning early undercounts edges), completeness formula derivation; clicked: Union Find approach, per-root node/edge tracking, merge logic

Graph View