Count the Number of Complete Components

Count the Number of Complete Components

What is this problem about?

In the Count the Number of Complete Components coding problem, you are given an undirected graph with $n$ nodes. A "complete component" is a connected component where every node is directly connected to every other node in that same component (essentially a "clique" that is not part of a larger connected group).

Your goal is to find the total number of such complete components in the graph.

Why is this asked in interviews?

Microsoft and Amazon use this question to test a candidate's ability to combine graph interview pattern traversal with property verification. It requires identifying disjoint sets of nodes and then validating a mathematical property of those sets. It evaluations whether you can distinguish between "connected" and "fully connected."

Algorithmic pattern used

The problem can be solved using Graph Traversal (BFS/DFS) or Union Find.

1. Use BFS or DFS to find all connected components.
2. For each component found:
   • Count the number of nodes in the component ($V$).
   • Count the number of edges in the component ($E$).
   • A complete graph with $V$ vertices must have exactly $\frac{V imes (V - 1)}{2}$ edges.
3. If the edge count matches this formula, increment your result.

Example explanation

Graph with nodes 0, 1, 2 and 3, 4. Edges: (0,1), (1,2), (0,2) and (3,4).

1. Component 1: {0, 1, 2}. $V = 3, E = 3$.
   • Formula: $\frac{3 imes 2}{2} = 3$. Match! (Complete)
2. Component 2: {3, 4}. $V = 2, E = 1$.
   • Formula: $\frac{2 imes 1}{2} = 1$. Match! (Complete) Total complete components = 2.

If edge (0,2) was missing:

1. Component 1: {0, 1, 2}. $V = 3, E = 2$.
   • Formula: 3. No match! (Not complete) Total = 1.

Common mistakes candidates make

• Miscounting edges: If using an adjacency list, remember that each edge (u, v) might be counted twice (once for $u$ and once for $v$). Divide by 2 to get the actual $E$.
• Incomplete search: Failing to visit all nodes in a component.
• Union Find edge tracking: If using Union Find, candidates often forget to track the edge count within the data structure.

Interview preparation tip

When working with undirected graphs, always clarify if you need to find connected components first. Once you have a component isolated, checking properties (like being a tree, a cycle, or a complete graph) becomes a much simpler task.