Count the Number of Complete Components — Problem & Solution
Count the Number of Complete Components solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count the Number of Complete Components is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon, Google and Salesforce interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Breadth-First Search, Graph, Union Find
- Asked at: Amazon, Google, Salesforce
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An undirected graph has n vertices labelled 0 … n - 1. A connected component is complete when every pair of its vertices is joined by an edge.
Return the number of complete connected components.
Example 1
Input: n = 6, edges = [[0,1],[0,2],[1,2],[3,4]]
Output: 3
Explanation: The triangle `{0,1,2}`, the pair `{3,4}` and the lone vertex `5`.
Example 2
Input: n = 6, edges = [[0,1],[0,2],[1,2],[3,4],[3,5]]
Output: 1
Explanation: `{3,4,5}` is a path, not a triangle.
Example 3
Input: n = 1, edges = []
Output: 1
Explanation: A single vertex is complete on its own.
Constraints
1 <= n <= 500 <= edges.length <= n * (n - 1) / 2edges[i].length == 20 <= edges[i][0], edges[i][1] <= n - 1edges[i][0] != edges[i][1]There are no repeated edges.
Hints for Count the Number of Complete Components
Hint 1
A component with
svertices is complete exactly when it holdss · (s - 1) / 2edges.Hint 2
So you only need each component's vertex count and edge count.
Hint 3
Union-find gives both in one pass over the edges.
How to solve Count the Number of Complete Components
Reduce "every pair joined" to a count. A complete graph on s vertices has exactly s · (s - 1) / 2 edges, so tally vertices and edges per component and compare.
Approach
- Union the endpoints of every edge.
- Count
nodes[root]over the vertices andlinks[root]over the edges. - A root is complete when
2 · links == nodes · (nodes - 1).
Why it works
The edge count is sufficient because the graph has no repeated edges: with s vertices and no duplicates the maximum possible edge count is s · (s - 1) / 2, and reaching it forces every pair to be present. Comparing 2 · links to nodes · (nodes - 1) keeps the test in integers with no division.
Complexity
- Time —
O(n + m · α(n)) - Space —
O(n)
Pitfalls
- A component of size 1 has 0 edges, and
1 * 0 == 0makes the test pass without a special case. - An isolated vertex is a complete component of size 1 with 0 edges.
- Dividing by 2 invites a rounding bug; multiply the other side instead.
Reference solution
Python
from typing import List
def countCompleteComponents(n: int, edges: List[List[int]]) -> int:
parent = list(range(n))
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for u, v in edges:
a, b = find(u), find(v)
if a != b:
parent[b] = a
nodes = [0] * n
links = [0] * n
for i in range(n):
nodes[find(i)] += 1
for u, _ in edges:
links[find(u)] += 1
count = 0
for i in range(n):
if find(i) != i:
continue
if links[i] * 2 == nodes[i] * (nodes[i] - 1):
count += 1
return countJava
private static int[] ccParent;
private static int ccFind(int x) {
while (ccParent[x] != x) {
ccParent[x] = ccParent[ccParent[x]];
x = ccParent[x];
}
return x;
}
public static int countCompleteComponents(int n, int[][] edges) {
ccParent = new int[n];
for (int i = 0; i < n; i++) ccParent[i] = i;
for (int[] e : edges) {
int a = ccFind(e[0]), b = ccFind(e[1]);
if (a != b) ccParent[b] = a;
}
int[] nodes = new int[n];
int[] links = new int[n];
for (int i = 0; i < n; i++) nodes[ccFind(i)]++;
for (int[] e : edges) links[ccFind(e[0])]++;
int count = 0;
for (int i = 0; i < n; i++) {
if (ccFind(i) != i) continue;
if (links[i] * 2 == nodes[i] * (nodes[i] - 1)) count++;
}
return count;
}C++
int countCompleteComponents(int n, vector<vector<int>>& edges) {
vector<int> parent(n);
for (int i = 0; i < n; i++) parent[i] = i;
function<int(int)> find = [&](int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
for (auto& e : edges) {
int a = find(e[0]), b = find(e[1]);
if (a != b) parent[b] = a;
}
vector<int> nodes(n, 0), links(n, 0);
for (int i = 0; i < n; i++) nodes[find(i)]++;
for (auto& e : edges) links[find(e[0])]++;
int count = 0;
for (int i = 0; i < n; i++) {
if (find(i) != i) continue;
if (links[i] * 2 == nodes[i] * (nodes[i] - 1)) count++;
}
return count;
}JavaScript
var countCompleteComponents = function(n, edges) {
var i;
var parent = [];
for (i = 0; i < n; i++) parent.push(i);
var find = function(x) {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
for (i = 0; i < edges.length; i++) {
var a = find(edges[i][0]), b = find(edges[i][1]);
if (a !== b) parent[b] = a;
}
var nodes = [], links = [];
for (i = 0; i < n; i++) { nodes.push(0); links.push(0); }
for (i = 0; i < n; i++) nodes[find(i)]++;
for (i = 0; i < edges.length; i++) links[find(edges[i][0])]++;
var count = 0;
for (i = 0; i < n; i++) {
if (find(i) !== i) continue;
if (links[i] * 2 === nodes[i] * (nodes[i] - 1)) count++;
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)