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.
Example 1:

Input: n = 6, edges = [[0,1],[0,2],[1,2],[3,4]] Output: 3 Explanation: From the picture above, one can see that all of the components of this graph are complete.
Example 2:

Input: n = 6, edges = [[0,1],[0,2],[1,2],[3,4],[3,5]] Output: 1 Explanation: The component containing vertices 0, 1, and 2 is complete since there is an edge between every pair of two vertices. On the other hand, the component containing vertices 3, 4, and 5 is not complete since there is no edge between vertices 4 and 5. Thus, the number of complete components in this graph is 1.
Constraints:
1 <= n <= 500 <= edges.length <= n * (n - 1) / 2edges[i].length == 20 <= ai, bi <= n - 1ai != biWhen you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
We want to find groups of connected things where everything in the group is directly connected to everything else in the group. The brute force way checks every possible group of things to see if it meets this connection requirement.
Here's how the algorithm would work step-by-step:
def count_complete_components_brute_force(number_of_nodes, edges):
all_possible_groups = []
# Initially, each node is its own group.
for node_index in range(number_of_nodes):
all_possible_groups.append({node_index})
# Iterate through all possible pairs of nodes to merge groups.
for first_node in range(number_of_nodes):
for second_node in range(first_node + 1, number_of_nodes):
if (first_node, second_node) in edges or (second_node, first_node) in edges:
# Merge the groups containing the connected nodes.
first_group_index = -1
second_group_index = -1
for index, group in enumerate(all_possible_groups):
if first_node in group:
first_group_index = index
if second_node in group:
second_group_index = index
if first_group_index != second_group_index:
all_possible_groups[first_group_index].update(all_possible_groups[second_group_index])
del all_possible_groups[second_group_index]
# Update group indices after deletion
first_group_index = -1
second_group_index = -1
for index, group in enumerate(all_possible_groups):
if first_node in group:
first_group_index = index
if second_node in group:
second_group_index = index
complete_components_count = 0
# Check each group for completeness.
for group in all_possible_groups:
is_complete = True
group_list = list(group)
for first_node_index in range(len(group_list)):
for second_node_index in range(first_node_index + 1, len(group_list)):
# Check all possible node pairs
if (group_list[first_node_index], group_list[second_node_index]) not in edges and \
(group_list[second_node_index], group_list[first_node_index]) not in edges:
is_complete = False
break
if not is_complete:
break
# Only increase if all pairs are connected
if is_complete:
complete_components_count += 1
return complete_components_countThe problem asks us to find separate groups of nodes in a graph where every node in the group is connected to every other node in that group. We can efficiently do this by exploring each group and checking if all the possible connections exist within that group.
Here's how the algorithm would work step-by-step:
def count_complete_components(number_of_nodes, edges):
graph = [[] for _ in range(number_of_nodes)]
for node1, node2 in edges:
graph[node1].append(node2)
graph[node2].append(node1)
visited = [False] * number_of_nodes
complete_components_count = 0
for node in range(number_of_nodes):
if not visited[node]:
node_count = 0
edge_count = 0
queue = [node]
group_nodes = []
visited[node] = True
while queue:
current_node = queue.pop(0)
node_count += 1
group_nodes.append(current_node)
for neighbor in graph[current_node]:
edge_count += 1
if not visited[neighbor]:
visited[neighbor] = True
queue.append(neighbor)
# Divide edge_count by 2 because each edge is counted twice
edge_count //= 2
# Check for complete component
if node_count * (node_count - 1) // 2 == edge_count:
complete_components_count += 1
return complete_components_count| Case | How to Handle |
|---|---|
| Empty graph (n=0, edges=[]) | Return 0 since there are no components. |
| Graph with only one node (n=1, edges=[]) | Return 1 since a single node is a complete component. |
| Graph with no edges (n>1, edges=[]) | Return n, as each node is a separate complete component. |
| Fully connected graph (every node connected to every other) | Return 1 since the entire graph is one complete component. |
| Graph with multiple disconnected components, some complete, some not | The algorithm should correctly identify and count only the complete components by verifying all possible edges exist within each component. |
| Graph with a single large complete component and several isolated nodes | Correctly identify the large component and count the remaining isolated nodes as complete components as well. |
| Maximum number of nodes and edges, check for efficient algorithm and memory usage | Use an algorithm with O(n + m) complexity (where n is the number of nodes and m is the number of edges), such as Depth First Search or Breadth First Search to avoid timeouts. |
| Graph containing self-loops (edge from node i to itself) | Ignore self-loops as they don't contribute to determining if a component is complete. |