Count the Number of Complete Components — Editorial

Opening the reading…

Intuitioncomplete means containing every possible internal edge

Start with the definition of a complete component. If a component contains m vertices, every pair of those vertices must have an edge, so it must contain exactly m * (m - 1) / 2 edges. The formula counts choices of two different vertices: choose the first endpoint in m ways and the second in m - 1 ways, then divide by two because each edge was counted from both directions.

The graph may contain several components, so first determine which vertices belong together. Union-Find gives every vertex a representative for its connected component. Once all edges have been joined, count the vertices and edges belonging to each representative. A component is complete precisely when its actual edge count reaches the formula's maximum.

Isolated vertices fit the same rule without a special case. For m = 1, the required number of edges is zero, which matches an isolated vertex. This is why the solution can process all component representatives uniformly instead of treating single-vertex components separately.

Approachjoin first, aggregate second, classify last

Create one Union-Find set for every vertex, with each vertex initially representing its own component, because isolated vertices must remain visible even when they occur in no edge.

Process every edge with unite(a, b), merging the sets of its endpoints, because any vertices connected by an edge must receive the same final component representative.

Run find on every vertex and increment compSize[root], because counting vertices by their current array position would split one component across outdated representatives.

Run through every edge again and increment compEdges[find(a)], because both endpoints are already in the same component and each undirected edge should contribute exactly once.

Inspect only indices i where find(i) == i, because those indices are the component representatives; checking every array slot would count the same component once for each non-root vertex.

For a representative with m vertices, compare its edge count with m * (m - 1) / 2, because that is the largest possible number of undirected edges among those m vertices.

Increment the answer when the counts match and return it, because a connected component with the maximum possible internal edge count has an edge between every pair of its vertices.

Complexitythe inverse Ackermann factor comes from Union-Find

MEASURE	BOUND	WHY
Time	O((n + e) alpha(n))	There are n vertex finds for component sizes, e edge finds for component edge counts, and e unions. Path compression and union by rank make each operation amortized alpha(n), so no edge or vertex causes more than this nearly constant amortized work.
Space	O(n)	The parent, rank, component-size, and component-edge arrays each have n entries. The returned integer is output storage and is excluded from the extra-space bound. The bound does not degrade with the graph's shape because Union-Find stores one record per vertex rather than one record per possible edge.

Here n is the number of vertices and e is the number of edges.

Annotated solutionC++ · Union-Find with path compression and union by rank

CPPJoin all endpoints, aggregate each root's vertices and edges, then compare with the complete-graph formula.

#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>
using namespace std;

class Solution {
public:
    int countCompleteComponents(int n, vector<vector<int>>& edges) {
        vector<int> parent(n), rankValue(n, 0);
        iota(parent.begin(), parent.end(), 0);

        function<int(int)> find = [&](int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        };

        auto unite = [&](int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return;
            }

            if (rankValue[rootX] < rankValue[rootY]) {
                swap(rootX, rootY);
            }
            parent[rootY] = rootX;

            if (rankValue[rootX] == rankValue[rootY]) {
                rankValue[rootX]++;
            }
        };

        for (const vector<int>& edge : edges) {
            unite(edge[0], edge[1]);
        }

        vector<int> componentSize(n, 0);
        vector<int> componentEdges(n, 0);

        for (int vertex = 0; vertex < n; vertex++) {
            componentSize[find(vertex)]++;
        }

        for (const vector<int>& edge : edges) {
            componentEdges[find(edge[0])]++;
        }

        int answer = 0;
        for (int vertex = 0; vertex < n; vertex++) {
            if (find(vertex) != vertex) {
                continue;
            }

            int vertices = componentSize[vertex];
            int requiredEdges = vertices * (vertices - 1) / 2;
            if (componentEdges[vertex] == requiredEdges) {
                answer++;
            }
        }

        return answer;
    }
};

The two passes after all unions are deliberate. componentSize must use final roots, and componentEdges must use those same final roots. Counting while unions are still happening could attach data to a representative that later becomes a child. Delaying aggregation avoids moving counts whenever two sets merge.

The traversal alternativesame test, explicit adjacency storage

A DFS or BFS solution is equally natural: build an adjacency list, discover one component, count its vertices, and sum their degrees. The degree sum is twice the number of internal edges, so divide it by two before applying the complete-graph formula. This is not asymptotically faster than Union-Find; it trades the compact parent arrays for adjacency storage and makes the component traversal explicit.

CPPIterative DFS counts a component's vertices and converts its degree sum into an edge count.

#include <vector>
using namespace std;

class Solution {
public:
    int countCompleteComponents(int n, vector<vector<int>>& edges) {
        vector<vector<int>> graph(n);
        for (const vector<int>& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        vector<bool> visited(n, false);
        int answer = 0;

        for (int start = 0; start < n; start++) {
            if (visited[start]) {
                continue;
            }

            int vertices = 0;
            int degreeSum = 0;
            vector<int> stack = {start};
            visited[start] = true;

            while (!stack.empty()) {
                int vertex = stack.back();
                stack.pop_back();
                vertices++;
                degreeSum += static_cast<int>(graph[vertex].size());

                for (int neighbor : graph[vertex]) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        stack.push_back(neighbor);
                    }
                }
            }

            int actualEdges = degreeSum / 2;
            int requiredEdges = vertices * (vertices - 1) / 2;
            if (actualEdges == requiredEdges) {
                answer++;
            }
        }

        return answer;
    }
};

The DFS version uses O(n + e) extra space because the adjacency list stores both directions of every edge, while the Union-Find version uses O(n) extra space. Both take O(n + e) time here up to the nearly constant Union-Find factor. Prefer DFS or BFS when you already need to inspect neighbors; prefer Union-Find when the main operation is merging groups.