Count the Number of Complete Components

Medium
933.

Count the Number of Complete Components

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.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
var countCompleteComponents = function(n, edges) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.

Hints for Count the Number of Complete Components

  1. Hint 1

    A component with s vertices is complete exactly when it holds s · (s - 1) / 2 edges.

  2. Hint 2

    So you only need each component's vertex count and edge count.

  3. 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

  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

Java

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)