#2685

Medium

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Count the Number of Complete Components

Determine the number of complete connected components in an undirected graph using efficient traversal techniques and graph analysis.

depth first search breadth first search union find graph

Problem Statement

Given an integer n representing the number of vertices in an undirected graph numbered from 0 to n-1, and a 2D array edges where edges[i] = [ai, bi] indicates an undirected edge between ai and bi, determine the number of complete connected components. Each component is complete if every pair of vertices within it shares an edge, forming a fully connected subgraph.

A connected component is defined as a set of vertices where a path exists between any two vertices, and no vertex has an edge connecting outside the component. Return the total number of these complete components in the given graph.

Examples

Example 1

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

Output: 3

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

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 <= 50
0 <= edges.length <= n * (n - 1) / 2
edges[i].length == 2
0 <= ai, bi <= n - 1
ai != bi
There are no repeated edges.

Solution Approach

Use DFS or BFS to Identify Components

Traverse the graph using depth-first search or breadth-first search to group vertices into connected components. Keep track of visited nodes to avoid revisiting and ensure that each component is explored fully.

Check Component Completeness

For each discovered component, verify that every pair of vertices has a direct edge. Count the component only if all internal pairs are connected, which ensures it forms a complete subgraph.

Optimize with Union Find

Optionally, apply Union Find to efficiently merge vertices and track component sizes. After forming all sets, check each set's internal connections to determine completeness without repeatedly traversing the same edges.

Complexity Analysis

Metric	Value
Time	O(n + m\alpha(n))
Space	O(n)

Time complexity is O(n + mα(n)) where n is vertices and m is edges, accounting for Union Find operations. Space complexity is O(n) for tracking visited nodes or parent arrays in Union Find.

What Interviewers Usually Probe

Pay attention if the candidate correctly identifies all connected components using DFS or BFS.
Check if the solution validates completeness efficiently without redundant edge checks.
Watch for proper handling of small graphs and edge cases with single-node components.

Common Pitfalls or Variants

Common pitfalls

Forgetting to check every vertex pair in a component can overcount incomplete components.
Revisiting nodes without marking them can lead to infinite loops or wrong component counts.
Assuming all components with edges are complete without verifying full connectivity within each.

Follow-up variants

Count only components with exactly k vertices that are complete.
Determine the largest complete component in terms of vertex count.
Handle weighted graphs where completeness requires all edges to exceed a threshold weight.

FAQ

What is a complete connected component in this problem?

A complete connected component is a subset of vertices where every vertex pair is directly connected by an edge, forming a fully connected subgraph.

Can I use BFS instead of DFS to solve Count the Number of Complete Components?

Yes, BFS can traverse the graph in the same way as DFS to identify connected components, allowing you to check completeness afterward.

Why might Union Find be helpful for this problem?

Union Find can efficiently group vertices into components and track connectivity, reducing repeated traversal when verifying completeness.

How do I handle isolated vertices?

Isolated vertices count as complete components of size one since they trivially satisfy the completeness condition.

What is the expected complexity using DFS or BFS?

Using DFS or BFS, the time complexity is O(n + m) and space is O(n), covering all vertices and edges once while checking component completeness.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:
        def dfs(i: int) -> (int, int):
            vis[i] = True
            x, y = 1, len(g[i])
            for j in g[i]:
                if not vis[j]:
                    a, b = dfs(j)
                    x += a
                    y += b
            return x, y

        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        vis = [False] * n
        ans = 0
        for i in range(n):
            if not vis[i]:
                a, b = dfs(i)
                ans += a * (a - 1) == b
        return ans

Solution 2: Simple Method

Problems needed to solve：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:
        def dfs(i: int) -> (int, int):
            vis[i] = True
            x, y = 1, len(g[i])
            for j in g[i]:
                if not vis[j]:
                    a, b = dfs(j)
                    x += a
                    y += b
            return x, y

        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        vis = [False] * n
        ans = 0
        for i in range(n):
            if not vis[i]:
                a, b = dfs(i)
                ans += a * (a - 1) == b
        return ans

Continue Practicing

#2493 divide nodes into the maximum number of groups #2492 minimum score of a path between two cities #2368 reachable nodes with restrictions