2685. Count the Number of Complete Components

DFS
BFS
Union Find
Graph

TIME

O(n + m * alpha(n))

SPACE

O(n)

Intuition

A connected component with k vertices is complete precisely when it contains every possible edge, i.e. exactly k * (k - 1) / 2 of them. So for each component we just need its vertex count and edge count and compare.

Approach

Group vertices into components with union-find (or DFS/BFS).
For each component, tally:
- V = number of vertices,
- E = number of edges whose endpoints are in the component (each undirected edge counted once).
The component is complete iff E == V * (V - 1) / 2. Count such components.

With union-find: after unioning all edges, count vertices per root and edges per root (an edge belongs to the root of its endpoints), then check the formula per root.

Complexity

Time: O(n + m · α(n)), near-linear with union-find
Space: O(n)

Edge Cases

Single isolated vertex → V=1, E=0, and 1*0/2 = 0 → complete (counts)
Component with a missing edge → not complete (Example 2)
No edges at all → every vertex is its own complete component → answer n
Self-loops don't occur (a_i != b_i), and no duplicate edges, so E is exact

Code

from typing import List


class Solution:
    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:
        """
        2685. Count the Number of Complete Components
        Time: O(n + m * alpha(n))
        Space: O(n)
        """
        parent = list(range(n))
        size = [1] * n

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(a: int, b: int) -> None:
            ra, rb = find(a), find(b)
            if ra != rb:
                if size[ra] < size[rb]:
                    ra, rb = rb, ra
                parent[rb] = ra
                size[ra] += size[rb]

        for a, b in edges:
            union(a, b)

        # Count edges per component root.
        edge_count = {}
        for a, b in edges:
            r = find(a)
            edge_count[r] = edge_count.get(r, 0) + 1

        result = 0
        for v in range(n):
            if find(v) == v:  # v is a root
                k = size[v]
                if edge_count.get(v, 0) == k * (k - 1) // 2:
                    result += 1
        return result

import java.util.HashMap;
import java.util.Map;

/**
 * 2685. Count the Number of Complete Components
 * Time: O(n + m * alpha(n))
 * Space: O(n)
 */
class Solution {
    private int[] parent;
    private int[] size;

    public int countCompleteComponents(int n, int[][] edges) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }

        for (int[] e : edges) {
            union(e[0], e[1]);
        }

        // Count edges per component root.
        Map<Integer, Integer> edgeCount = new HashMap<>();
        for (int[] e : edges) {
            int r = find(e[0]);
            edgeCount.merge(r, 1, Integer::sum);
        }

        int result = 0;
        for (int v = 0; v < n; v++) {
            if (find(v) == v) { // v is a root
                long k = size[v];
                if (edgeCount.getOrDefault(v, 0) == k * (k - 1) / 2) {
                    result++;
                }
            }
        }
        return result;
    }

    private int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    private void union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra != rb) {
            if (size[ra] < size[rb]) {
                int t = ra;
                ra = rb;
                rb = t;
            }
            parent[rb] = ra;
            size[ra] += size[rb];
        }
    }
}