LeetCode 2685 - Count the Number of Complete Components

Difficulty: 🟡 Medium
Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory

Solution

Problem Understanding

This problem asks us to count how many connected components in an undirected graph are complete graphs.

We are given an integer n, representing the number of vertices labeled from 0 to n - 1, and a list of undirected edges. Each edge [a, b] means there is a bidirectional connection between node a and node b.

The graph may consist of multiple disconnected parts, called connected components. A connected component is a group of vertices where every node can reach every other node through some path, and no node in the group connects to vertices outside the group.

The key requirement is determining whether each connected component is complete. A component is complete if every pair of distinct vertices inside the component has a direct edge between them.

For example, if a component contains k vertices, then it is complete only if it contains exactly:

$$\frac{k \times (k - 1)}{2}$$

edges, because that is the number of unique vertex pairs in a fully connected graph.

The expected output is the number of connected components satisfying this completeness property.

The constraints are relatively small:

1 <= n <= 50
0 <= edges.length <= n * (n - 1) / 2

Since n is at most 50, even algorithms with quadratic or cubic behavior are acceptable. This gives us flexibility in implementation, allowing straightforward graph traversal techniques such as Depth-First Search (DFS), Breadth-First Search (BFS), or Union-Find.

Several edge cases are important to recognize upfront. A graph with no edges means every node forms an isolated component of size 1, and a single node is always a complete component because there are no missing pairwise connections. Another case is partially connected groups, where one edge is missing from an otherwise dense component. Such components must not be counted. The problem also guarantees there are no duplicate edges and no self-loops, which simplifies correctness because edge counting remains reliable.

Approaches

Brute Force Approach

A straightforward solution is to first identify every connected component, then explicitly verify whether every pair of nodes inside that component has a direct connection.

We can perform DFS or BFS to collect all nodes in a connected component. Once we have the component, suppose it contains k nodes. We then check all possible node pairs. For every pair (u, v), we verify whether an edge exists between them.

To support fast lookup, we would maintain an adjacency set for each node. For a component of size k, checking all pairs requires O(k²) time.

This method is correct because it directly validates the definition of a complete graph. However, it performs unnecessary pairwise checking. Since completeness depends only on the total number of edges, we can do better conceptually.

Optimal Approach

The key insight is that a connected component with k vertices is complete if and only if it contains exactly:

$$\frac{k(k-1)}{2}$$

edges.

Instead of checking every pair explicitly, we can perform DFS or BFS to gather:

The number of vertices in the component.
The total degree sum of the component.

Because every undirected edge contributes 2 to the degree sum, the number of actual edges becomes:

$$\text{edge count} = \frac{\text{degree sum}}{2}$$

After traversing a component, we compare:

$$\text{actual edges}$$

with

$$\frac{k(k-1)}{2}$$

If they match, the component is complete.

This avoids repeated pairwise validation and uses graph properties more elegantly.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n + e)	Traverses components and explicitly checks every node pair
Optimal	O(n + e)	O(n + e)	Counts vertices and edges during DFS

Since n <= 50, both approaches work comfortably, but the optimal solution scales better and is more elegant.

Algorithm Walkthrough

We will use Depth-First Search (DFS) to discover connected components and determine whether each component is complete.

Build an adjacency list for the graph.

Since the graph is undirected, every edge [u, v] is added to both graph[u] and graph[v]. This structure allows efficient traversal of neighboring nodes. 2. Create a visited array.

This prevents revisiting nodes and ensures each connected component is processed exactly once. 3. Iterate through all vertices from 0 to n - 1.

Whenever we encounter an unvisited node, it represents the start of a new connected component. 4. Perform DFS on the component.

During DFS, track two quantities:

node_count, the number of vertices in the component.
degree_sum, the total number of neighbor connections across all component nodes.

For each visited node:

Mark it as visited.
Increment node_count.
Add len(graph[node]) to degree_sum.
Continue DFS for unvisited neighbors.

Compute the actual number of edges.

Since every edge appears twice in an undirected graph:

$$\text{actual edges} = \frac{\text{degree sum}}{2}$$ 6. Compute the expected number of edges.

For a complete graph with k nodes:

$$\text{expected edges} = \frac{k(k-1)}{2}$$ 7. Compare the two values.

If the actual edge count equals the expected edge count, increment the answer because this component is complete. 8. Continue until all nodes are processed.

Return the total number of complete connected components.

Why it works

The algorithm relies on a fundamental graph property: a connected component with k vertices is complete exactly when it contains every possible pairwise edge, which equals k(k-1)/2.

DFS guarantees that every node in a connected component is visited exactly once, allowing us to accurately count both nodes and edges. Since each undirected edge contributes twice to the degree sum, dividing by 2 gives the true edge count. Comparing this count with the theoretical maximum uniquely determines completeness.

Python Solution

from typing import List

class Solution:
    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:
        graph = [[] for _ in range(n)]

        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        visited = [False] * n
        complete_components = 0

        def dfs(node: int) -> tuple[int, int]:
            visited[node] = True

            node_count = 1
            degree_sum = len(graph[node])

            for neighbor in graph[node]:
                if not visited[neighbor]:
                    child_nodes, child_degree_sum = dfs(neighbor)
                    node_count += child_nodes
                    degree_sum += child_degree_sum

            return node_count, degree_sum

        for node in range(n):
            if not visited[node]:
                node_count, degree_sum = dfs(node)

                actual_edges = degree_sum // 2
                expected_edges = node_count * (node_count - 1) // 2

                if actual_edges == expected_edges:
                    complete_components += 1

        return complete_components

The implementation begins by constructing an adjacency list to represent the graph efficiently. Since the graph is undirected, every edge is stored in both directions.

A visited array ensures nodes are processed once. Whenever an unvisited node is found, DFS explores the entire connected component.

The dfs helper function returns two values: the total number of nodes in the component and the total degree sum. For each node, the function adds its neighbor count and recursively explores unvisited neighbors.

After DFS completes, the algorithm calculates the actual edge count by dividing the degree sum by 2, because undirected edges are counted twice. It then computes the expected number of edges for a complete graph and compares them. If the values match, the component is complete.

Go Solution

func countCompleteComponents(n int, edges [][]int) int {
	graph := make([][]int, n)

	for _, edge := range edges {
		u, v := edge[0], edge[1]
		graph[u] = append(graph[u], v)
		graph[v] = append(graph[v], u)
	}

	visited := make([]bool, n)
	completeComponents := 0

	var dfs func(int) (int, int)

	dfs = func(node int) (int, int) {
		visited[node] = true

		nodeCount := 1
		degreeSum := len(graph[node])

		for _, neighbor := range graph[node] {
			if !visited[neighbor] {
				childNodes, childDegreeSum := dfs(neighbor)
				nodeCount += childNodes
				degreeSum += childDegreeSum
			}
		}

		return nodeCount, degreeSum
	}

	for node := 0; node < n; node++ {
		if !visited[node] {
			nodeCount, degreeSum := dfs(node)

			actualEdges := degreeSum / 2
			expectedEdges := nodeCount * (nodeCount - 1) / 2

			if actualEdges == expectedEdges {
				completeComponents++
			}
		}
	}

	return completeComponents
}

The Go implementation closely mirrors the Python version. The adjacency list is built using slices, and a recursive DFS function returns both the node count and degree sum.

Go does not support nested named functions in the same way as Python, so DFS is implemented as a function variable using closure syntax.

Integer overflow is not a concern here because n <= 50, meaning the maximum possible number of edges is only 1225. Slice handling is straightforward because Go slices naturally grow using append.

Worked Examples

Example 1

Input:

n = 6
edges = [[0,1],[0,2],[1,2],[3,4]]

Adjacency list:

Node	Neighbors
0	[1, 2]
1	[0, 2]
2	[0, 1]
3	[4]
4	[3]
5	[]

Component 1: `{0,1,2}`

DFS traversal:

Step	Node	Node Count	Degree Sum
1	0	1	2
2	1	2	4
3	2	3	6

Calculation:

Metric	Value
Nodes	3
Actual Edges	6 / 2 = 3
Expected Edges	3 × 2 / 2 = 3

This component is complete.

Component 2: `{3,4}`

Metric	Value
Nodes	2
Degree Sum	2
Actual Edges	1
Expected Edges	1

This component is complete.

Component 3: `{5}`

Metric	Value
Nodes	1
Degree Sum	0
Actual Edges	0
Expected Edges	0

This component is complete.

Final answer:

Example 2

Input:

n = 6
edges = [[0,1],[0,2],[1,2],[3,4],[3,5]]

Component 1: `{0,1,2}`

Metric	Value
Nodes	3
Actual Edges	3
Expected Edges	3

This component is complete.

Component 2: `{3,4,5}`

Metric	Value
Nodes	3
Degree Sum	4
Actual Edges	2
Expected Edges	3

This component is not complete because edge (4,5) is missing.

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + e)	Each node and edge is visited once during DFS
Space	O(n + e)	Adjacency list plus recursion stack and visited array

The graph traversal visits every vertex once and every edge twice, once from each endpoint. Since the graph is undirected, this results in linear complexity relative to the graph size.

The adjacency list stores all vertices and edges, and the recursion stack can grow up to O(n) in the worst case for a deeply connected component.

Test Cases

solution = Solution()

assert solution.countCompleteComponents(
    6,
    [[0, 1], [0, 2], [1, 2], [3, 4]]
) == 3  # Provided example with three complete components

assert solution.countCompleteComponents(
    6,
    [[0, 1], [0, 2], [1, 2], [3, 4], [3, 5]]
) == 1  # Provided example with one incomplete component

assert solution.countCompleteComponents(
    1,
    []
) == 1  # Single isolated node

assert solution.countCompleteComponents(
    4,
    []
) == 4  # All isolated nodes are complete

assert solution.countCompleteComponents(
    3,
    [[0, 1], [1, 2], [0, 2]]
) == 1  # Fully connected triangle

assert solution.countCompleteComponents(
    3,
    [[0, 1], [1, 2]]
) == 0  # Connected but incomplete graph

assert solution.countCompleteComponents(
    5,
    [[0, 1], [2, 3], [3, 4], [2, 4]]
) == 2  # One pair and one triangle

assert solution.countCompleteComponents(
    5,
    [[0, 1], [1, 2], [2, 3], [3, 4]]
) == 0  # Chain graph is not complete

assert solution.countCompleteComponents(
    4,
    [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]
) == 1  # Fully connected K4 graph

assert solution.countCompleteComponents(
    5,
    [[0, 1], [1, 2], [0, 2], [3, 4]]
) == 2  # Triangle and pair

Test	Why
`n=6`, triangle + pair + isolated node	Validates provided example
`n=6`, incomplete component	Verifies missing edge detection
`n=1`, no edges	Tests smallest input
`n=4`, no edges	Confirms isolated nodes are complete
Triangle graph	Verifies complete component recognition
Simple chain	Ensures connected does not imply complete
Pair + triangle	Tests multiple complete components
Long chain	Verifies incomplete larger component
Complete K4	Tests dense graph correctness
Triangle + pair	Verifies multiple components

Edge Cases

Isolated Nodes

A node with no edges forms a connected component of size 1. This is a subtle edge case because it may seem disconnected, but it is still considered complete. A complete graph with one vertex requires 0 edges, which matches the formula:

$$\frac{1 \times (1 - 1)}{2} = 0$$

The implementation handles this naturally because DFS visits the node, finds zero neighbors, and correctly identifies the component as complete.

Connected but Incomplete Components

A component may be connected but still fail completeness. For example:

0 - 1 - 2

All nodes are reachable, so this is one connected component. However, node 0 and node 2 are not directly connected, meaning the graph is not complete.

The implementation catches this by comparing actual edges against the expected count. Since the edge total is smaller than required, the component is rejected.

Multiple Disconnected Components

The graph may contain several disconnected groups, some complete and some incomplete. A common bug is failing to reset component tracking variables or revisiting nodes.

The implementation avoids this issue using the visited array. Every DFS traversal processes exactly one component independently, ensuring counts remain accurate across the entire graph.

LeetCode 2685 - Count the Number of Complete Components

Solution

Problem Understanding

Approaches

Brute Force Approach

Optimal Approach

Algorithm Walkthrough

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Component 1: {0,1,2}

Component 2: {3,4}

Component 3: {5}

Example 2

Component 1: {0,1,2}

Component 2: {3,4,5}

Complexity Analysis

Test Cases

Edge Cases

Isolated Nodes

Connected but Incomplete Components

Multiple Disconnected Components

Component 1: `{0,1,2}`

Component 2: `{3,4}`

Component 3: `{5}`

Component 1: `{0,1,2}`

Component 2: `{3,4,5}`