Problem of The Day: Count the Number of Complete Components
Problem Statement
Intuition
This algorithm aims to determine the number of complete connected components in an undirected graph. A complete component is a connected subgraph where every node is directly connected to every other node within the component.
Approach
- Union-Find Data Structure
- Initialize a Union-Find (Disjoint Set Union) data structure to efficiently manage connected components.
- The
findmethod implements path compression for efficient lookups. - The
unionmethod connects two nodes, merging their components while maintaining rank to optimize merging.
-
Building Components
- Traverse the given edge list and use the
unionfunction to group connected nodes. - After processing all edges, apply
findon each node to ensure all connections are properly linked. - Use a dictionary to store nodes grouped by their root representatives.
- Traverse the given edge list and use the
- Checking Completeness
- Iterate over each component and verify if all possible edges exist between its nodes.
- If any expected edge is missing, the component is not complete.
- Count only the complete components.
Complexity
-
Time Complexity:
- Union-Find operations: The
findandunionoperations run in nearly constant time, i.e., O(α(n)), where α is the inverse Ackermann function. - Edge processing: O(E), where E is the number of edges.
- Completeness check: In the worst case, O(V²) where V is the number of nodes in a component.
- Overall, the worst-case complexity is O(V² + E).
- Union-Find operations: The
-
Space Complexity:
- O(V) for storing parent/root and rank arrays.
- O(V) for the components dictionary.
- Total space complexity is O(V + E).
Code
from collections import defaultdict
from typing import List
class UnionFind:
def __init__(self, n):
self.root = [i for i in range(n)]
self.rank = [0] * n
self.num_of_components = n
def find(self, x):
if self.root[x] == x:
return x
self.root[x] = self.find(self.root[x]) # Path compression
return self.root[x]
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX == rootY:
return
if self.rank[rootX] < self.rank[rootY]:
self.root[rootX] = rootY
elif self.rank[rootX] > self.rank[rootY]:
self.root[rootY] = rootX
else:
self.root[rootY] = rootX
self.rank[rootX] += 1
self.num_of_components -= 1
class Solution:
def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:
if not edges:
return n
uf = UnionFind(n)
components = defaultdict(list)
for x, y in edges:
uf.union(x, y)
for i in range(n):
uf.find(i) # Ensure proper root assignment
for i, root in enumerate(uf.root):
components[root].append(i)
res = uf.num_of_components
for root, nodes in components.items():
n = len(nodes)
is_completed = True
for i in range(n):
p = nodes[i]
for j in range(i + 1, n):
q = nodes[j]
if [p, q] not in edges and [q, p] not in edges:
is_completed = False
break
if not is_completed:
res -= 1
return max(res, 0)
Editorial
Approach 1: Adjacency List
class Solution:
def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:
# Adjacency lists for each vertex
graph = [[] for _ in range(n)]
# Map to store frequency of each unique adjacency list
component_freq = defaultdict(int)
# Initialize adjacency lists with self-loops
for vertex in range(n):
graph[vertex] = [vertex]
# Build adjacency lists from edges
for v1, v2 in edges:
graph[v1].append(v2)
graph[v2].append(v1)
# Count frequency of each unique adjacency pattern
for vertex in range(n):
neighbors = tuple(sorted(graph[vertex]))
component_freq[neighbors] += 1
# Count complete components where size equals frequency
return sum(
1
for neighbors, freq in component_freq.items()
if len(neighbors) == freq
)
Approach 2: Depth-First Search (DFS)
class Solution:
def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:
# Adjacency lists for each vertex
graph = defaultdict(list)
# Build adjacency lists from edges
for v1, v2 in edges:
graph[v1].append(v2)
graph[v2].append(v1)
complete_count = 0
visited = set()
def _dfs(curr: int, info: list) -> None:
visited.add(curr)
info[0] += 1 # Increment vertex count
info[1] += len(graph[curr]) # Add edges from current vertex
# Explore unvisited neighbors
for next_vertex in graph[curr]:
if next_vertex not in visited:
_dfs(next_vertex, info)
# Process each unvisited vertex
for vertex in range(n):
if vertex in visited:
continue
# info[0] = vertices count, info[1] = total edges count
component_info = [0, 0]
_dfs(vertex, component_info)
# Check if component is complete - edges should be vertices * (vertices-1)
if component_info[0] * (component_info[0] - 1) == component_info[1]:
complete_count += 1
return complete_count
Approach 3: Breadth-First Search (BFS)
class Solution:
def countCompleteComponents(self, n: int, edges: list[list[int]]) -> int:
# Create adjacency list representation of the graph
graph = [[] for _ in range(n)]
# Build graph from edges
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = [False] * n
complete_components = 0
# Process each unvisited vertex
for vertex in range(n):
if not visited[vertex]:
# BFS to find all vertices in the current component
component = []
queue = [vertex]
visited[vertex] = True
while queue:
current = queue.pop(0)
component.append(current)
# Process neighbors
for neighbor in graph[current]:
if not visited[neighbor]:
queue.append(neighbor)
visited[neighbor] = True
# Check if component is complete (all vertices have the right number of edges)
is_complete = True
for node in component:
if len(graph[node]) != len(component) - 1:
is_complete = False
break
if is_complete:
complete_components += 1
return complete_components
Approach 4: Disjoint Set Union (Union-Find)
class UnionFind:
def __init__(self, n):
self.parent = [-1] * n
self.size = [1] * n
def _find(self, node):
# Find root of component with path compression
if self.parent[node] == -1:
return node
self.parent[node] = self._find(self.parent[node])
return self.parent[node]
def _union(self, node_1, node_2):
# Union by size
root_1 = self._find(node_1)
root_2 = self._find(node_2)
if root_1 == root_2:
return
# Merge smaller component into larger one
if self.size[root_1] > self.size[root_2]:
self.parent[root_2] = root_1
self.size[root_1] += self.size[root_2]
else:
self.parent[root_1] = root_2
self.size[root_2] += self.size[root_1]
class Solution:
def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:
# Initialize Union Find and edge counter
dsu = UnionFind(n)
edge_count = {}
# Connect components using edges
for edge in edges:
dsu._union(edge[0], edge[1])
# Count edges in each component
for edge in edges:
root = dsu._find(edge[0])
edge_count[root] = edge_count.get(root, 0) + 1
# Check if each component is complete
complete_count = 0
for vertex in range(n):
if dsu._find(vertex) == vertex: # If vertex is root
node_count = dsu.size[vertex]
expected_edges = (node_count * (node_count - 1)) // 2
if edge_count.get(vertex, 0) == expected_edges:
complete_count += 1
return complete_count