Count how many connected components in an undirected graph are complete graphs.
You are given an undirected graph with vertices labeled from $0n-1$ and a list of edges. A connected component is called complete if every pair of distinct vertices inside that component is directly connected by an edge.
Your task is to return the number of connected components that are complete.
In other words, for each connected component, check whether it forms a clique: if the component has vertices, then it must contain exactly edges to be complete.
Input Format
- An integer representing the number of vertices.
- A list of undirected edges, where each edge is a pair .
Vertices are labeled from $0n-1$.
Output Format
- Return an integer: the number of connected components that are complete.
Constraints
- The graph is undirected.
- No self-loops are assumed.
- Parallel edges are not required for the standard interpretation of this problem.
Example 1
Input
n = 6 edges = [[0,1],[0,2],[1,2],[3,4]]
Output
2
Explanation
The graph has three connected components: {0,1,2}, {3,4}, and {5}. The first is complete because all 3 pairs are connected. The second is also complete because a 2-node connected component needs exactly 1 edge. The isolated vertex {5} is complete by definition. So the answer is 3.
Note: if using the standard LeetCode interpretation, every isolated vertex is a complete component.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.