What is the time complexity of LeetCode 2316. Count Unreachable Pairs of Nodes in an Undirected Graph?

The Python solution on this page runs in O(n + m).

What is the space complexity of LeetCode 2316. Count Unreachable Pairs of Nodes in an Undirected Graph?

The Python solution on this page uses O(n + m) auxiliary space.

Count Unreachable Pairs of Nodes in an Undirected Graph — LeetCode 2316 Python Solution

MediumDepth-First SearchBreadth-First SearchUnion FindGraph

Problem: #2316
Pattern: Union-Find
Reading time: 3 min
Source: leetcode.com

The problem

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

Example

Input: n = 3, edges = [[0,1],[0,2],[1,2]]
Output: 0
Explanation: There are no pairs of nodes that are unreachable from each other. Therefore, we return 0.

Python solution

Python

class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        def dfs(i: int) -> int:
            if vis[i]:
                return 0
            vis[i] = True
            return 1 + sum(dfs(j) for j in g[i])

        g = [[] for _ in range(n)]
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        vis = [False] * n
        ans = s = 0
        for i in range(n):
            t = dfs(i)
            ans += s * t
            s += t
        return ans

Complexity

Measure	Complexity
Time	O(n + m)
Space	O(n + m) auxiliary

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 2316. Count Unreachable Pairs of Nodes in an Undirected Graph 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 2316. Count Unreachable Pairs of Nodes in an Undirected Graph?: LeetCode 2316. Count Unreachable Pairs of Nodes in an Undirected Graph is rated Medium on LeetCode.
What is the time complexity of LeetCode 2316. Count Unreachable Pairs of Nodes in an Undirected Graph?: The Python solution on this page runs in O(n + m).
What is the space complexity of LeetCode 2316. Count Unreachable Pairs of Nodes in an Undirected Graph?: The Python solution on this page uses O(n + m) auxiliary space.
What topics does LeetCode 2316. Count Unreachable Pairs of Nodes in an Undirected Graph cover?: LeetCode 2316. Count Unreachable Pairs of Nodes in an Undirected Graph is tagged Depth-First Search, Breadth-First Search, Union Find and Graph on LeetCode.