How hard is LeetCode 2685. Count the Number of Complete Components?

LeetCode 2685. Count the Number of Complete Components is rated Medium on LeetCode.

What is the time complexity of LeetCode 2685. Count the Number of Complete Components?

The Python solution on this page runs in O(V+E).

What is the space complexity of LeetCode 2685. Count the Number of Complete Components?

The Python solution on this page uses O(V) auxiliary space.

What topics does LeetCode 2685. Count the Number of Complete Components cover?

LeetCode 2685. Count the Number of Complete Components is tagged Depth-First Search, Breadth-First Search, Union Find and Graph on LeetCode.

Count the Number of Complete Components — LeetCode 2685 Python Solution

MediumDepth-First SearchBreadth-First SearchUnion FindGraph

Problem: #2685
Pattern: Union-Find
Reading time: 4 min
Source: leetcode.com

The problem

You are given an integer n. There is an undirected graph with n vertices, numbered from 0 to n - 1.

Example

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.

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(V+E)
Space	O(V) auxiliary

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 2685. Count the Number of Complete Components is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.

The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2685. Count the Number of Complete Components?: LeetCode 2685. Count the Number of Complete Components is rated Medium on LeetCode.
What is the time complexity of LeetCode 2685. Count the Number of Complete Components?: The Python solution on this page runs in O(V+E).
What is the space complexity of LeetCode 2685. Count the Number of Complete Components?: The Python solution on this page uses O(V) auxiliary space.
What topics does LeetCode 2685. Count the Number of Complete Components cover?: LeetCode 2685. Count the Number of Complete Components is tagged Depth-First Search, Breadth-First Search, Union Find and Graph on LeetCode.