Count the Number of Complete Components
Problem
Given an undirected graph with n nodes and edge list edges, a connected component is "complete" iff every pair of its nodes is directly connected. Return the number of complete connected components.
n = 6, edges = [[0,1],[0,2],[1,2],[3,4]]3def count_complete_components(n, edges):
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v); adj[v].append(u)
seen = [False] * n
ans = 0
for s in range(n):
if seen[s]: continue
stack = [s]
seen[s] = True
verts, edeg = 0, 0
while stack:
u = stack.pop()
verts += 1
edeg += len(adj[u])
for v in adj[u]:
if not seen[v]:
seen[v] = True
stack.append(v)
if edeg == verts * (verts - 1):
ans += 1
return ansfunction countCompleteComponents(n, edges) {
const adj = Array.from({ length: n }, () => []);
for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
const seen = new Array(n).fill(false);
let ans = 0;
for (let s = 0; s < n; s++) {
if (seen[s]) continue;
const stack = [s]; seen[s] = true;
let verts = 0, edeg = 0;
while (stack.length) {
const u = stack.pop();
verts++;
edeg += adj[u].length;
for (const v of adj[u]) {
if (!seen[v]) { seen[v] = true; stack.push(v); }
}
}
if (edeg === verts * (verts - 1)) ans++;
}
return ans;
}class Solution {
public int countCompleteComponents(int n, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
boolean[] seen = new boolean[n];
int ans = 0;
for (int s = 0; s < n; s++) {
if (seen[s]) continue;
Deque<Integer> stack = new ArrayDeque<>();
stack.push(s); seen[s] = true;
int verts = 0, edeg = 0;
while (!stack.isEmpty()) {
int u = stack.pop();
verts++;
edeg += adj.get(u).size();
for (int v : adj.get(u)) {
if (!seen[v]) { seen[v] = true; stack.push(v); }
}
}
if (edeg == verts * (verts - 1)) ans++;
}
return ans;
}
}int countCompleteComponents(int n, vector<vector<int>>& edges) {
vector<vector<int>> adj(n);
for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); }
vector<bool> seen(n, false);
int ans = 0;
for (int s = 0; s < n; s++) {
if (seen[s]) continue;
stack<int> st; st.push(s); seen[s] = true;
int verts = 0, edeg = 0;
while (!st.empty()) {
int u = st.top(); st.pop();
verts++;
edeg += adj[u].size();
for (int v : adj[u]) {
if (!seen[v]) { seen[v] = true; st.push(v); }
}
}
if (edeg == verts * (verts - 1)) ans++;
}
return ans;
}Explanation
A component is "complete" when every pair of its nodes is directly connected. The neat shortcut is to count the nodes and edges of each connected piece, then check one formula: a group of V nodes is complete exactly when it has V·(V-1)/2 edges — that is the number of possible pairs.
We build an undirected adjacency list and then explore each component with a DFS using a stack. While exploring, we tally verts (how many nodes we touched) and edeg (the sum of degrees of those nodes).
Why compare edeg == verts * (verts - 1) instead of dividing by 2? Because the degree sum counts every edge twice. So 2·E = V·(V-1) is the same complete-graph test, just without the division — it avoids fractions.
Example: component {0,1,2} with edges 0-1, 0-2, 1-2. Each node has degree 2, so edeg = 6 and verts = 3. Check: 3·2 = 6 matches, so it is complete.
A lone node {5} has verts=1, edeg=0, and 1·0 = 0 matches too, so singletons count as complete. We add 1 for every component that passes the test.