2685. Count the Number of Complete Components

LeetCode

Problem

We are given an undirected graph with n vertices labeled from 0 to n - 1 and an edge list. A connected component is considered "complete" if every pair of distinct vertices within it is directly connected by an edge. In other words, for a component with V vertices, it must have exactly V * (V - 1) / 2 edges. The task is to count the number of complete connected components in the graph.

Solution Description

To solve the problem:

Build the graph as an adjacency list (an array of sets), where each vertex stores its neighbors.
Use Depth-First Search (DFS) to traverse the graph and collect the vertices for each connected component while maintaining a visited array.
For each component, verify that every vertex in the component is connected to all other vertices by counting its neighbors (within the component) and ensuring the count equals component length - 1.
Increment a counter for each complete component and return this count.

The overall time complexity is O(n + E) and the space complexity is O(n).

Example

Example 1: Input: n = 6, edges = [[0,1],[0,2],[1,2],[3,4]] Output: 3 Explanation: The components are [0,1,2] (a triangle), [3,4] (an edge), and the isolated vertex [5]; all are complete.

Example 2: Input: n = 6, edges = [[0,1],[0,2],[1,2],[3,4],[3,5]] Output: 1 Explanation: The component [0,1,2] is complete; the component [3,4,5] is not complete (missing an edge between 4 and 5).

References

https://en.wikipedia.org/wiki/Connected_component_(graph_theory) https://en.wikipedia.org/wiki/Complete_graph

Solution

2025-03-22 Count the Number of Complete Components - LeetCode leetcode.com

/**
 * @param {number} n - Number of vertices in the graph.
 * @param {number[][]} edges - List of edges, where each edge is represented as [u, v].
 * @return {number} - The count of complete components.
 */
var countCompleteComponents = function(n, edges) {
    // debug

    const log = typeof NestedInteger !== 'undefined' ? () => {} : console.log;
    const table = typeof NestedInteger !== 'undefined' ? () => {} : console.table;

    // make graph
    const graph = Array.from({ length: n }, () => new Set());
    for (const [src, dest] of edges) {
        graph[src].add(dest);
        graph[dest].add(src);
    }

    log('GRAPH');
    log(graph);

    //
    const visited = new Array(n).fill(false);
    let completeCount = 0;

    function dfs(node, component) {
        visited[node] = true;
        component.push(node);
        for (const neighbor of graph[node]) {
            if (visited[neighbor]) continue;
            dfs(neighbor, component);
        }
    }


    for (let i = 0; i < n; i++) {
        if (visited[i]) continue;
        const component = [];
        dfs(i, component);

        const compSet = new Set(component);
        let isComplete = true;
        for (const node of component) {
            let count = 0;
            for (const dest of graph[node]) {
                if (compSet.has(dest)) {
                    count++;
                }
            }
            if (count !== component.length - 1) {
                isComplete = false;
                break;
            }
        }
        if (isComplete) {
            completeCount++;
        }
    }

    return completeCount;
};

// Test cases: LitCode examples come first.
const testCases = [
    // LitCode Example 1:
    { n: 6, edges: [[0,1],[0,2],[1,2],[3,4]], expected: 3 },
    // LitCode Example 2:
    { n: 6, edges: [[0,1],[0,2],[1,2],[3,4],[3,5]], expected: 1 },
    // Additional tests:
    { n: 3, edges: [[0,1],[1,2],[2,0]], expected: 1 },
    { n: 4, edges: [[0,1],[1,2],[2,3],[3,0],[0,2]], expected: 0 },
    { n: 4, edges: [[0,1],[0,2],[0,3]], expected: 0 },
    { n: 1, edges: [], expected: 1 },
    { n: 5, edges: [[0,1],[1,2]], expected: 2 },
    { n: 8, edges: [[0,1],[1,2],[2,0],[3,4],[4,5],[5,3],[6,7]], expected: 3 },
];

testCases.forEach((test, index) => {
    const result = countCompleteComponents(test.n, test.edges);
    console.log(`Test Case ${index + 1}: ${result === test.expected ? 'Passed' : 'Failed'} (Expected: ${test.expected}, Got: ${result})`);
});