Count the Number of Complete Components

main.md

Question

Approach

I perform BFS on each unvisited node to gather all nodes in a connected component. I then count the number of nodes and edges in that component. A complete component of size k must have exactly k*(k-1)/2 edges.

Implementation

class Solution:
    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:
        graph = defaultdict(set)
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)

        visited = [False] * n
        complete_components = 0

        for i in range(n):
            if not visited[i]:
                queue = deque([i])
                visited[i] = True
                nodes = [i]
                edge_count = 0

                while queue:
                    node = queue.popleft()
                    for neighbor in graph[node]:
                        edge_count += 1
                        if not visited[neighbor]:
                            visited[neighbor] = True
                            queue.append(neighbor)
                            nodes.append(neighbor)

                edge_count //= 2
                size = len(nodes)
                if edge_count == size * (size - 1) // 2:
                    complete_components += 1

        return complete_components

Complexities

• Time: O(n + e)
• Space: O(n + e)