2793. Count the Number of Complete Components
My accepted Python solution to LeetCode problem 2793, Count the Number of Complete Components, running in 70ms.
- Difficulty: Medium
- Python
- Runtime 70ms
- Memory 18.3MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 70ms, memory 18.3MB, accepted 2026-01-01.
class Solution:
def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:
from collections import defaultdict
# Build adjacency list
graph = defaultdict(set)
for a, b in edges:
graph[a].add(b)
graph[b].add(a)
visited = [False] * n
count = 0
def dfs(node, component):
visited[node] = True
component.append(node)
for neighbor in graph[node]:
if not visited[neighbor]:
dfs(neighbor, component)
for i in range(n):
if not visited[i]:
component = []
dfs(i, component)
# Check if this component is complete
k = len(component)
# A complete graph with k vertices has k*(k-1)/2 edges
expected_edges = k * (k - 1) // 2
# Count actual edges in this component
actual_edges = 0
for node in component:
actual_edges += len(graph[node])
actual_edges //= 2 # Each edge counted twice
if actual_edges == expected_edges:
count += 1
return count