Get started

Count the Number of Complete Components — Medium Problem & Solution

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.

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 <= 50
  • 0 <= edges.length <= n * (n - 1) / 2
  • edges[i].length == 2
  • 0 <= edges[i][0], edges[i][1] <= n - 1
  • edges[i][0] != edges[i][1]
  • There are no repeated 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

  1. Union the endpoints of every edge.
  2. Count nodes[root] over the vertices and links[root] over the edges.
  3. 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 == 0 makes 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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 65 breadth-first search problems · the whole catalogue