Count the Number of Complete Components
Problem link: https://leetcode.com/problems/count-the-number-of-complete-components/
Problem Statement
You are given an integer n representing the number of nodes in an undirected graph labeled from 0 to n - 1, and an array edges where edges[i] = [u, v] indicates an edge between nodes u and v.
Return the number of complete connected components of the graph.
A connected component is complete if there is an edge between every pair of nodes in the component.
Input
Integer n (number of nodes) 2D array edges[][] representing undirected edges
Output
Return an integer representing the number of complete connected components.
Example
Input: n = 6 edges = [[0,1],[0,2],[1,2],[3,4]]
Output: 2
Explanation
Component 1: {0,1,2} → complete (all pairs connected) Component 2: {3,4} → complete Component 3: {5} → single node, also complete Total = 3 (but depends on example variation)
Brute Force
Intuition
For each component, check every pair of nodes and verify if an edge exists between them.
Approach
- Build adjacency matrix
- Find connected components
- For each component of size k:
- Check all pairs (i, j)
- If any pair is missing → not complete
- Count valid components
Dry Run
Component {0,1,2} → check pairs (0,1),(0,2),(1,2) All exist → valid Component {3,4} → valid Component {5} → valid
Visualization
Code (Java)
import java.util.*;
public class Solution {
public int countCompleteComponents(int n, int[][] edges) {
boolean[][] mat = new boolean[n][n];
for (int[] e : edges) {
mat[e[0]][e[1]] = true;
mat[e[1]][e[0]] = true;
}
boolean[] visited = new boolean[n];
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
List<Integer> comp = new ArrayList<>();
dfs(i, mat, visited, comp);
boolean complete = true;
for (int u : comp) {
for (int v : comp) {
if (u != v && !mat[u][v]) {
complete = false;
}
}
}
if (complete) count++;
}
}
return count;
}
void dfs(int node, boolean[][] mat, boolean[] visited, List<Integer> comp) {
visited[node] = true;
comp.add(node);
for (int i = 0; i < mat.length; i++) {
if (mat[node][i] && !visited[i]) {
dfs(i, mat, visited, comp);
}
}
}
}
Complexity Analysis
Checking all pairs in each component leads to O(n^2) time due to adjacency matrix.
Optimal Solution
Intuition
A component is complete if number of edges = k*(k-1)/2 where k = number of nodes.
Approach
- Build adjacency list
- DFS to find component
- Count nodes (k) and total edges (sum of degrees / 2)
- If edges == k*(k-1)/2 → complete
- Count such components
Dry Run
Component {0,1,2}: k=3, edges=3 → 3 == 3 → valid Component {3,4}: k=2, edges=1 → valid Component {5}: k=1, edges=0 → valid
Code (Java)
import java.util.*;
public 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[] visited = new boolean[n];
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
int[] nodes = new int[1];
int[] edgesCount = new int[1];
dfs(i, adj, visited, nodes, edgesCount);
int k = nodes[0];
int totalEdges = edgesCount[0] / 2;
if (totalEdges == k * (k - 1) / 2) count++;
}
}
return count;
}
void dfs(int node, List<List<Integer>> adj, boolean[] visited, int[] nodes, int[] edgesCount) {
visited[node] = true;
nodes[0]++;
edgesCount[0] += adj.get(node).size();
for (int nei : adj.get(node)) {
if (!visited[nei]) {
dfs(nei, adj, visited, nodes, edgesCount);
}
}
}
}
Complexity Analysis
Each node and edge is processed once. Edge counting avoids pairwise checking.
Quick Revision (Brute Force)
- Find component
- Check every pair
- Time O(n^2)
Quick Revision (Optimal)
- k nodes → need k*(k-1)/2 edges
- Count edges using degree sum
- Time O(n+e)