Watch 10 video solutions for Count the Number of Complete Components, a medium level problem involving Depth-First Search, Breadth-First Search, Union Find. This walkthrough by NeetCodeIO has 8,218 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 != biProblem Overview: You are given an undirected graph with n nodes and a list of edges. The task is to count how many connected components are complete graphs. A component is complete when every pair of distinct nodes inside it has an edge between them. For a component with k nodes, the total number of edges must be k * (k - 1) / 2.
Approach 1: Using Sorting (O(E log E) time, O(E) space)
This method starts by sorting the edge list so that edges belonging to the same node range appear together. After sorting, you iterate through the edges and group nodes into components while counting how many edges belong to each group. For every component discovered, track two values: the number of nodes and the number of edges encountered. Once traversal for a component finishes, compute the expected edge count using k * (k - 1) / 2. If the actual edge count matches this value, the component is complete. Sorting makes it easier to process related edges sequentially and simplifies component grouping when the edge list is large or initially unordered.
Approach 2: Using a Hash Map (O(V + E) time, O(V + E) space)
This approach builds an adjacency list using a hash map where each node maps to its neighbors. Then traverse the graph using Depth-First Search or Breadth-First Search to explore one connected component at a time. During traversal, count how many nodes belong to the component and sum the degrees of those nodes. Since each undirected edge contributes twice to the degree count, divide the total degree by two to get the actual edge count. After finishing the traversal, verify whether the component satisfies the complete graph condition edges == k * (k - 1) / 2. Hash map adjacency lists provide constant-time neighbor lookups and make this method scale well for sparse graphs.
This problem is fundamentally a connected component analysis task combined with a mathematical property of complete graphs. Graph traversal guarantees that every node in a component is visited exactly once. The edge-count validation step ensures that the component is fully connected internally. Similar ideas appear in problems involving graph validation and connectivity checks, often implemented with Union Find or DFS.
Recommended for interviews: The hash map + DFS/BFS approach is the expected solution. It runs in linear time O(V + E) and demonstrates clear understanding of graph traversal and component analysis. The sorting-based approach works but adds unnecessary overhead due to O(E log E) sorting. Showing the traversal solution signals stronger graph fundamentals.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Using Sorting | O(E log E) | O(E) | When edges must be processed in ordered groups or the input edge list is highly unordered |
| Using Hash Map + DFS/BFS | O(V + E) | O(V + E) | Best general solution for graph traversal and connected component detection |