Count the Number of Complete Components - Practice Coding Problems

Count the Number of Complete Components - Problem

You are given an integer n. There is an undirected graph with n vertices, numbered from 0 to n - 1. You are given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting vertices ai and bi.

Return the number of complete connected components of the graph.

A connected component is a subgraph of a graph in which there exists a path between any two vertices, and no vertex of the subgraph shares an edge with a vertex outside of the subgraph.

A connected component is said to be complete if there exists an edge between every pair of its vertices.

Input & Output

Example 1 — Mixed Components

$ Input: n = 6, edges = [[0,1],[0,2],[1,2],[3,4]]

› Output: 3

💡 Note: Component {0,1,2} has 3 vertices and 3 edges, needs 3×2/2=3 edges ✓. Component {3,4} has 2 vertices and 1 edge, needs 2×1/2=1 edge ✓. Component {5} is single vertex ✓. Total: 3 complete components.

Example 2 — No Edges

$ Input: n = 4, edges = []

› Output: 4

💡 Note: No edges means 4 isolated vertices: {0}, {1}, {2}, {3}. Each single vertex forms a complete component by definition.

Example 3 — Incomplete Triangle

$ Input: n = 3, edges = [[0,1],[1,2]]

› Output: 0

💡 Note: Component {0,1,2} has 3 vertices but only 2 edges. For completeness, needs 3×2/2=3 edges. Missing edge (0,2), so not complete.

Constraints

1 ≤ n ≤ 50
0 ≤ edges.length ≤ n × (n - 1) / 2
edges[i].length == 2
0 ≤ ai, bi ≤ n - 1
ai ≠ bi
There are no repeated edges.

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Graph with vertices 0-5 and given edges

Find Components

Use DFS to identify connected components

Check Completeness

Count complete components using k×(k-1)/2 formula

Key Takeaway

🎯 Key Insight: A complete component with k vertices must have exactly k×(k-1)/2 edges - this is the complete graph formula

Asked in

M Meta 8 G Google 6 a Amazon 4

The key insight is that a complete component with k vertices must have exactly k×(k-1)/2 edges. Best approach uses DFS to find connected components then verifies completeness by counting edges. Time: O(n + m), Space: O(n + m)

Common Approaches

Approach	Time	Space	Notes
✓ DFS - Find Connected Components	O(n + m)	O(n + m)	Use DFS to find all connected components, then check if each is complete
Brute Force - Check All Subsets	O(2ⁿ × n²)	O(n)	Generate all possible subsets and check if each forms a complete connected component

DFS - Find Connected Components — Algorithm Steps

Build adjacency list from edges
Use DFS to find all connected components
For each component, count vertices and edges
Check if edge count equals k*(k-1)/2

Visualization

Tap to expand

Step-by-Step Walkthrough

DFS Traversal

Visit all vertices in each connected component

Count Edges

Count edges within each component

Check Formula

Verify if edge count equals k*(k-1)/2

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int** graph;
int* graphSizes;
bool* visited;

void dfs(int node, int* component, int* componentSize) {
    visited[node] = true;
    component[(*componentSize)++] = node;
    
    for (int i = 0; i < graphSizes[node]; i++) {
        int neighbor = graph[node][i];
        if (!visited[neighbor]) {
            dfs(neighbor, component, componentSize);
        }
    }
}

int solution(int n, int edges[][2], int edgesSize) {
    // Build adjacency list
    graph = (int**)malloc(n * sizeof(int*));
    graphSizes = (int*)calloc(n, sizeof(int));
    visited = (bool*)calloc(n, sizeof(bool));
    
    // Count neighbors for each vertex
    for (int i = 0; i < edgesSize; i++) {
        graphSizes[edges[i][0]]++;
        graphSizes[edges[i][1]]++;
    }
    
    // Allocate memory for adjacency lists
    for (int i = 0; i < n; i++) {
        graph[i] = (int*)malloc(graphSizes[i] * sizeof(int));
        graphSizes[i] = 0; // Reset to use as index
    }
    
    // Fill adjacency lists
    for (int i = 0; i < edgesSize; i++) {
        int u = edges[i][0], v = edges[i][1];
        graph[u][graphSizes[u]++] = v;
        graph[v][graphSizes[v]++] = u;
    }
    
    int completeComponents = 0;
    
    // Find all connected components
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            int component[n];
            int componentSize = 0;
            dfs(i, component, &componentSize);
            
            // Check if this component is complete
            if (componentSize == 1) {
                completeComponents++;
            } else {
                // Count edges within this component
                int edgeCount = 0;
                bool inComponent[n];
                memset(inComponent, false, sizeof(inComponent));
                
                for (int j = 0; j < componentSize; j++) {
                    inComponent[component[j]] = true;
                }
                
                for (int j = 0; j < componentSize; j++) {
                    int u = component[j];
                    for (int k = 0; k < graphSizes[u]; k++) {
                        int v = graph[u][k];
                        if (inComponent[v] && u < v) { // Avoid double counting
                            edgeCount++;
                        }
                    }
                }
                
                // A complete graph with k vertices has k*(k-1)/2 edges
                if (edgeCount == componentSize * (componentSize - 1) / 2) {
                    completeComponents++;
                }
            }
        }
    }
    
    // Free memory
    for (int i = 0; i < n; i++) {
        free(graph[i]);
    }
    free(graph);
    free(graphSizes);
    free(visited);
    
    return completeComponents;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    scanf(" %[^\n]", line);
    
    // Parse edges array
    int edges[1000][2];
    int edgesSize = 0;
    
    if (strcmp(line, "[]") != 0) {
        char* ptr = line + 1; // Skip '['
        while (*ptr && *ptr != ']') {
            if (*ptr == '[') {
                ptr++;
                edges[edgesSize][0] = atoi(ptr);
                while (*ptr && *ptr != ',') ptr++;
                ptr++; // Skip ','
                edges[edgesSize][1] = atoi(ptr);
                while (*ptr && *ptr != ']') ptr++;
                ptr++; // Skip ']'
                edgesSize++;
            }
            ptr++;
        }
    }
    
    int result = solution(n, edges, edgesSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

DFS visits each vertex once and each edge twice, where n is vertices and m is edges

✓ Linear Growth

Space Complexity

O(n + m)

Adjacency list storage plus recursion stack for DFS

⚡ Linearithmic Space

18.9K Views

Medium Frequency

~25 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS - Find Connected Components — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler