LeetCode Solutions Blog

Count the Number of Complete Components

Number: 2793

Difficulty: Medium

Paid? No

Problem Description

Given an undirected graph with n vertices (labeled from 0 to n - 1) and a list of undirected edges, count the number of connected components that form complete graphs (i.e. each pair of vertices in the component is directly connected by an edge).

Key Insights

Find connected components using DFS, BFS, or Union Find.
For each connected component, determine if it is a complete graph.
A connected component of size k must have exactly k*(k-1)/2 edges to be complete.
Use an adjacency list (or similar) to represent the graph.

Space and Time Complexity

Time Complexity: O(n + m) where n is the number of vertices and m is the number of edges; each vertex and edge is processed at most once. Space Complexity: O(n + m) for storing the graph and visited information.

Solution

The solution builds an adjacency list from the input edges. Then, it traverses the graph (using DFS, for example) to identify all connected components. For each component, it counts the number of vertices and the number of edges (keeping in mind that each edge is counted twice if iterating over all vertices of the component). A component is complete if the number of edges equals k*(k-1)/2, where k is the number of vertices in that component. Finally, the solution returns the count of complete components.

Code Solutions

def countCompleteComponents(n, edges):
    # Build the graph using an adjacency list
    graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    visited = [False] * n
    complete_components = 0

    def dfs(node):
        # Initialize component info: vertices and edge count (each edge counted twice)
        stack = [node]
        vertices = []
        while stack:
            current = stack.pop()
            if not visited[current]:
                visited[current] = True
                vertices.append(current)
                # Add unseen neighbors
                for neighbor in graph[current]:
                    if not visited[neighbor]:
                        stack.append(neighbor)
        return vertices

    for i in range(n):
        if not visited[i]:
            component = dfs(i)
            k = len(component)
            # Count edges in the component: sum degrees and then divide by 2.
            edge_count = 0
            for node in component:
                edge_count += len(graph[node])
            edge_count //= 2
            # Complete graph condition: number of edges equals k*(k-1)/2
            if edge_count == k * (k - 1) // 2:
                complete_components += 1

    return complete_components

# Example usage:
print(countCompleteComponents(6, [[0,1],[0,2],[1,2],[3,4]]))  # Output: 3
print(countCompleteComponents(6, [[0,1],[0,2],[1,2],[3,4],[3,5]]))  # Output: 1