Problem Description

You have an undirected graph with n vertices labeled from 0 to n - 1. The graph's edges are given as a 2D array edges, where each edges[i] = [ai, bi] represents an undirected edge between vertices ai and bi.

Your task is to count how many complete connected components exist in this graph.

A connected component is a group of vertices where:

• You can reach any vertex from any other vertex within the group by following edges
• No vertex in the group has an edge to any vertex outside the group

A connected component is complete when every vertex in the component is directly connected to every other vertex in that component by an edge. In other words, if a component has k vertices, it must have exactly k * (k - 1) / 2 edges to be complete (since every pair of vertices needs an edge between them).

For example:

• If you have 3 vertices that are all connected to each other (forming a triangle), that's a complete component
• If you have 3 vertices where only 2 edges exist (forming a line), that's NOT a complete component
• A single isolated vertex (with no edges) counts as a complete component

The solution uses DFS to identify each connected component, counting both the number of vertices and total degree (sum of edges) in each component. For a complete component with a vertices, the total degree sum should equal a * (a - 1) (since each vertex connects to all other a - 1 vertices, and each edge is counted twice in the degree sum).

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem explicitly states we have an undirected graph with n vertices and edges connecting them.

Is it a tree?

• No: The graph is not necessarily a tree. It can have multiple disconnected components, and each component might have cycles (especially since we're looking for complete components where every vertex connects to every other vertex).

Is the problem related to directed acyclic graphs?

• No: The graph is undirected, not directed, and we're not dealing with DAG-specific properties.

Is the problem related to shortest paths?

• No: We're not finding shortest paths between vertices. We're identifying and counting complete connected components.

Does the problem involve connectivity?

• Yes: The core of the problem is about finding connected components and determining if they are complete (fully connected within themselves).

Does the problem have small constraints?

• The constraints aren't explicitly stated in the problem, but for connectivity problems, we often need to explore all vertices in each component. DFS is a natural choice for exploring connected components.

Conclusion: The flowchart leads us to use DFS for this problem. DFS is perfect for:

1. Traversing each connected component completely
2. Counting the number of vertices in each component
3. Counting the total degree (number of edges) in each component
4. Determining if a component is complete by checking if the number of edges matches what's expected for a complete graph

The DFS approach allows us to visit each vertex once, mark it as visited, and gather the necessary information (vertex count and edge count) to determine if each component is complete.

Intuition

The key insight is recognizing what makes a connected component "complete". In a complete graph, every vertex must be connected to every other vertex. If we have k vertices in a complete component, then each vertex must have exactly k-1 edges (connecting to all other vertices).

This gives us a mathematical property to check: in a complete component with k vertices, there should be exactly k * (k-1) / 2 unique edges. But since we're working with an undirected graph where each edge is counted from both endpoints, when we sum up the degrees of all vertices in the component, we get k * (k-1) (each vertex has degree k-1, and we have k vertices).

So our strategy becomes:

1. Use DFS to explore each connected component
2. While exploring, count two things:
   • The number of vertices in the component
   • The sum of degrees (total number of edge endpoints) in the component
3. A component is complete if and only if: vertex_count * (vertex_count - 1) == total_degree_sum

Why does this work? Consider a triangle (3 vertices, all connected):

• Each vertex connects to 2 others, so each has degree 2
• Total degree sum = 3 × 2 = 6
• Expected for complete: 3 × (3-1) = 6 ✓

For an incomplete line of 3 vertices (A-B-C):

• A has degree 1, B has degree 2, C has degree 1
• Total degree sum = 4
• Expected for complete: 3 × 2 = 6 ✗

The DFS naturally handles disconnected components by starting fresh traversals from unvisited vertices, allowing us to check each component independently for completeness.

Learn more about Depth-First Search, Breadth-First Search, Union Find and Graph patterns.

Solution Approach

The implementation uses DFS with an adjacency list representation to efficiently explore and analyze each connected component.

Step 1: Build the Graph First, we construct an adjacency list using a defaultdict(list) to represent the undirected graph. For each edge [a, b], we add b to a's neighbor list and a to b's neighbor list:

g = defaultdict(list)
for a, b in edges:
    g[a].append(b)
    g[b].append(a)

Step 2: Initialize Tracking Variables We maintain a vis array of size n to track visited vertices, initially all set to False:

vis = [False] * n

Step 3: Define the DFS Function The DFS function returns two values for each component:

• x: the number of vertices in the component
• y: the sum of degrees in the component

def dfs(i: int) -> (int, int):
    vis[i] = True
    x, y = 1, len(g[i])  # Start with current vertex and its degree
    for j in g[i]:
        if not vis[j]:
            a, b = dfs(j)
            x += a  # Add vertices from subtree
            y += b  # Add degrees from subtree
    return x, y

The function marks vertex i as visited, initializes the count with 1 vertex (itself) and its degree len(g[i]), then recursively explores unvisited neighbors, accumulating their vertex and degree counts.

Step 4: Process All Components We iterate through all vertices, starting a new DFS for each unvisited vertex (which represents a new component):

ans = 0
for i in range(n):
    if not vis[i]:
        a, b = dfs(i)
        ans += a * (a - 1) == b

For each component found, we check if it's complete using the formula a * (a - 1) == b, where:

• a is the number of vertices
• b is the total degree sum
• The expression a * (a - 1) == b returns True (1) if complete, False (0) otherwise

The boolean result is implicitly converted to 0 or 1 and added to our answer counter.

Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges, as we visit each vertex and edge once.

Space Complexity: O(V + E) for the adjacency list and O(V) for the visited array and recursion stack.

Example Walkthrough

Let's walk through a concrete example with n = 6 vertices and edges = [[0,1], [0,2], [1,2], [3,4]].

Step 1: Build the Graph

First, we construct the adjacency list:

g[0] = [1, 2]
g[1] = [0, 2]
g[2] = [0, 1]
g[3] = [4]
g[4] = [3]
g[5] = []

We also initialize vis = [False, False, False, False, False, False].

Step 2: Process Component 1 (starting from vertex 0)

Start DFS from vertex 0:

• Mark vis[0] = True
• Initialize x = 1 (vertex 0), y = 2 (degree of vertex 0)
• Explore neighbor 1:
  • Mark vis[1] = True
  • At vertex 1: x = 1, y = 2 (degree of vertex 1)
  • Explore neighbor 2 from vertex 1:
    • Mark vis[2] = True
    • At vertex 2: x = 1, y = 2 (degree of vertex 2)
    • No unvisited neighbors, return (1, 2)
  • Back at vertex 1: accumulate to get x = 2, y = 4
  • Return (2, 4)
• Back at vertex 0: accumulate to get x = 3, y = 6

Component 1 has 3 vertices and total degree 6. Check: 3 * (3-1) = 6, which equals the degree sum. This is a complete component (triangle).

Step 3: Process Component 2 (starting from vertex 3)

Since vertices 0, 1, 2 are visited, we continue to vertex 3:

• Mark vis[3] = True
• Initialize x = 1, y = 1 (degree of vertex 3)
• Explore neighbor 4:
  • Mark vis[4] = True
  • At vertex 4: x = 1, y = 1 (degree of vertex 4)
  • No unvisited neighbors, return (1, 1)
• Back at vertex 3: accumulate to get x = 2, y = 2

Component 2 has 2 vertices and total degree 2. Check: 2 * (2-1) = 2, which equals the degree sum. This is a complete component (single edge).

Step 4: Process Component 3 (vertex 5)

Vertex 5 is unvisited and isolated:

• Mark vis[5] = True
• Initialize x = 1, y = 0 (degree of vertex 5)
• No neighbors to explore
• Return (1, 0)

Component 3 has 1 vertex and total degree 0. Check: 1 * (1-1) = 0, which equals the degree sum. This is a complete component (isolated vertex).

Final Answer: 3 complete connected components

Each component satisfied the completeness condition:

• Triangle (0-1-2): vertices=3, degree_sum=6, check: 3×2=6 ✓
• Edge (3-4): vertices=2, degree_sum=2, check: 2×1=2 ✓
• Isolated (5): vertices=1, degree_sum=0, check: 1×0=0 ✓

Solution Implementation

Time and Space Complexity

Time Complexity: O(V + E) where V is the number of vertices (n) and E is the number of edges.

• Building the adjacency list takes O(E) time as we iterate through all edges once.
• The DFS traversal visits each vertex exactly once, taking O(V) time for vertex visits.
• For each vertex, we iterate through its adjacency list. Since each edge is represented twice in the adjacency list (once for each endpoint), the total time spent iterating through adjacencies is O(2E) = O(E).
• The check a * (a - 1) == b for each component takes O(1) time.
• Overall: O(V + E)

Space Complexity: O(V + E)

• The adjacency list g stores all edges, requiring O(E) space (each edge appears twice).
• The visited array vis requires O(V) space.
• The recursion stack for DFS can go up to O(V) depth in the worst case (when the graph is a path).
• Overall: O(V + E)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Account for Double-Counting of Edges

The Pitfall: When building an undirected graph using an adjacency list, each edge is added twice (once for each direction). This means when we sum up the degrees of all vertices in a component, we're counting each edge twice. A common mistake is to compare this sum directly with k * (k - 1) / 2 (the number of edges in a complete graph) instead of k * (k - 1) (the doubled count).

Example of Incorrect Code:

# WRONG: Comparing with single edge count
if vertices * (vertices - 1) // 2 == edges:  # This would always fail!
    complete_component_count += 1

The Solution: Remember that in the adjacency list representation, the sum of degrees equals twice the number of edges. So for a complete component with k vertices:

• Number of actual edges: k * (k - 1) / 2
• Sum of degrees (what we calculate): k * (k - 1)

Correct Code:

# CORRECT: Account for double-counting
if vertices * (vertices - 1) == edges:
    complete_component_count += 1

2. Not Handling Isolated Vertices (Zero-Degree Nodes)

The Pitfall: If a vertex has no edges at all, it won't appear in the adjacency list when using a regular dictionary. This could lead to either missing these vertices entirely or getting a KeyError when trying to access them.

Example of Problematic Code:

# Using regular dict might miss isolated vertices
adjacency_list = {}
for u, v in edges:
    if u not in adjacency_list:
        adjacency_list[u] = []
    if v not in adjacency_list:
        adjacency_list[v] = []
    adjacency_list[u].append(v)
    adjacency_list[v].append(u)

# Later in DFS:
edge_count = len(adjacency_list[node])  # KeyError if node is isolated!

The Solution: Use defaultdict(list) which automatically creates an empty list for any new key access, ensuring isolated vertices return a degree of 0:

Correct Code:

from collections import defaultdict

adjacency_list = defaultdict(list)
for u, v in edges:
    adjacency_list[u].append(v)
    adjacency_list[v].append(u)

# Now len(adjacency_list[isolated_node]) returns 0 safely

3. Integer Division Instead of Exact Comparison

The Pitfall: Using integer division (//) when checking the complete component condition can lead to incorrect results due to rounding.

Example of Incorrect Code:

# WRONG: Integer division loses precision
expected_edges = vertices * (vertices - 1) // 2
actual_edges = edges // 2  # Dividing the double-counted sum
if expected_edges == actual_edges:
    complete_component_count += 1

The Solution: Keep the comparison in terms of the double-counted values to avoid any division:

Correct Code:

# CORRECT: Compare without division
if vertices * (vertices - 1) == edges:
    complete_component_count += 1

This approach is both more efficient (no division operation) and more accurate (no potential for rounding errors).