# Count Unreachable Pairs of Nodes in an Undirected Graph
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph)
Canonical: https://scaleengineer.com/dsa/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Graph
**Companies:** [Commvault](https://scaleengineer.com/companies/commvault)
---
## Problem
You are given an integer `n`. There is an **undirected** graph with `n` nodes, numbered from `0` to `n - 1`. You are given a 2D integer array `edges` where `edges[i] = [ai, bi]` denotes that there exists an **undirected** edge connecting nodes `ai` and `bi`.

Return _the **number of pairs** of different nodes that are **unreachable** from each other_.

**Example 1:**

![](https://assets.glich.co/dsa/count-unreachable-pairs-of-nodes-in-an-undirected-graph/image0.png) 

**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.

**Example 2:**

![](https://assets.glich.co/dsa/count-unreachable-pairs-of-nodes-in-an-undirected-graph/image1.png) 

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

**Constraints:**

* `1 <= n <= 105`
* `0 <= edges.length <= 2 * 105`
* `edges[i].length == 2`
* `0 <= ai, bi < n`
* `ai != bi`
* There are no repeated edges.

# Approaches
## Brute-Force Pairwise Reachability Check
This approach directly follows the problem definition by checking every possible pair of nodes. For each pair, it determines if they are connected by a path in the graph.
**Time:** O(N^2 * (N + E)). There are O(N^2) pairs. For each pair, we perform a graph traversal which takes O(N + E) time in the worst case. This is computationally prohibitive for the given constraints. · **Space:** O(N + E). O(N + E) for the adjacency list and O(N) for the `visited` array and queue/stack used in each traversal.
**Pros:** Simple to understand and implement directly from the problem definition.
**Cons:** Extremely inefficient and will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.; Performs a lot of redundant work by re-calculating reachability for nodes within the same component multiple times.
### Explanation
The algorithm iterates through all unique pairs of nodes `(i, j)` where `i < j`. For each pair, a graph traversal like Breadth-First Search (BFS) or Depth-First Search (DFS) is initiated from node `i`. The traversal explores all nodes reachable from `i`. If node `j` is not visited by the end of the traversal, the pair `(i, j)` is considered unreachable, and a counter is incremented. This process is repeated for all `n * (n - 1) / 2` pairs. First, an adjacency list representation of the graph is built from the `edges` array.
```java
public long countUnreachablePairs(int n, int[][] edges) {
    if (edges.length == 0) {
        return (long)n * (n - 1) / 2;
    }

    List<Integer>[] adj = new ArrayList[n];
    for (int i = 0; i < n; i++) {
        adj[i] = new ArrayList<>();
    }
    for (int[] edge : edges) {
        adj[edge[0]].add(edge[1]);
        adj[edge[1]].add(edge[0]);
    }

    long unreachableCount = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (!areConnected(i, j, n, adj)) {
                unreachableCount++;
            }
        }
    }
    return unreachableCount;
}

private boolean areConnected(int start, int end, int n, List<Integer>[] adj) {
    Queue<Integer> queue = new LinkedList<>();
    boolean[] visited = new boolean[n];

    queue.offer(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int node = queue.poll();
        if (node == end) {
            return true;
        }
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }
    return false;
}
```
### Algorithm
- Build an adjacency list representation of the graph.
- Initialize `unreachable_count = 0`.
- Loop for `i` from `0` to `n-1`.
- Inner loop for `j` from `i+1` to `n-1`.
- Inside the inner loop, call a function `areConnected(i, j)` which performs a BFS/DFS starting from `i`.
- If `areConnected` returns `false`, increment `unreachable_count`.
- Return `unreachable_count`.

## Graph Traversal (DFS/BFS) to Find Connected Components
A much more efficient approach is to realize that two nodes are unreachable if and only if they belong to different connected components. The problem then transforms into: find all connected components, get their sizes, and calculate the number of pairs of nodes that can be formed by picking one node from two different components.
**Time:** O(N + E). Building the adjacency list takes O(N + E). The main loop and the traversals together visit each node and edge exactly once. · **Space:** O(N + E), where N is the number of nodes and E is the number of edges. The adjacency list requires O(N + E) space. The `visited` array and the queue for BFS require O(N) space.
**Pros:** Efficient and guaranteed to pass within the time limits.; Conceptually clear, linking the problem to the fundamental graph concept of connected components.
**Cons:** Requires more space than a Union-Find approach, as the adjacency list can be large if E is large.
### Explanation
The core idea is to count the sizes of all disjoint connected components in the graph. Let the sizes of the `k` components be `s_1, s_2, ..., s_k`. A node in a component of size `s_i` is unreachable from any node in any other component `s_j` (where `j != i`). We can calculate the total number of unreachable pairs with a combinatorial trick. If we have processed some components and have `remaining_nodes` left to visit, and we find a new component of size `current_component_size`, then each of the `current_component_size` nodes is unreachable from each of the `remaining_nodes - current_component_size` nodes. We add `current_component_size * (remaining_nodes - current_component_size)` to our total and then update `remaining_nodes`.
The algorithm proceeds as follows:
1. Build an adjacency list for the graph.
2. Create a `visited` boolean array to keep track of visited nodes.
3. Initialize `unreachable_pairs = 0` and `remaining_nodes = n`.
4. Iterate from node `0` to `n-1`. If a node `i` has not been visited, it means we've found a new connected component.
5. Start a traversal (BFS or DFS) from `i` to find all nodes in this component and count its size.
6. Update the `unreachable_pairs` count and `remaining_nodes` using the size of the component just found.
7. Mark all nodes in the component as visited.
8. Continue until all nodes are visited.
```java
public long countUnreachablePairs(int n, int[][] edges) {
    List<Integer>[] adj = new ArrayList[n];
    for (int i = 0; i < n; i++) {
        adj[i] = new ArrayList<>();
    }
    for (int[] edge : edges) {
        adj[edge[0]].add(edge[1]);
        adj[edge[1]].add(edge[0]);
    }

    long unreachablePairs = 0;
    long remainingNodes = n;
    boolean[] visited = new boolean[n];

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            long currentComponentSize = 0;
            Queue<Integer> queue = new LinkedList<>();
            
            queue.offer(i);
            visited[i] = true;
            currentComponentSize++;

            while (!queue.isEmpty()) {
                int u = queue.poll();
                for (int v : adj[u]) {
                    if (!visited[v]) {
                        visited[v] = true;
                        currentComponentSize++;
                        queue.offer(v);
                    }
                }
            }
            
            unreachablePairs += currentComponentSize * (remainingNodes - currentComponentSize);
            remainingNodes -= currentComponentSize;
        }
    }
    return unreachablePairs;
}
```
### Algorithm
- Construct an adjacency list from the `edges`.
- Initialize a `visited` array of size `n` to all `false`.
- Initialize `unreachable_pairs = 0` and `remaining_nodes = n`.
- Iterate through each node `i` from `0` to `n-1`.
- If `visited[i]` is `false`:
  - Start a traversal (e.g., BFS) from `i`.
  - Count the number of nodes in the component (`component_size`).
  - Mark all nodes in the component as visited.
  - Add `component_size * (remaining_nodes - component_size)` to `unreachable_pairs`.
  - Subtract `component_size` from `remaining_nodes`.
- Return `unreachable_pairs`.

## Union-Find (Disjoint Set Union)
This approach uses a Disjoint Set Union (DSU) or Union-Find data structure, which is highly optimized for problems involving connected components or partitioning a set into disjoint subsets. It offers better space complexity than the traversal-based approach.
**Time:** O(N + E * α(N)), where α(N) is the Inverse Ackermann function. This function grows extremely slowly, so the complexity is nearly linear, i.e., O(N + E). · **Space:** O(N). The `parent` and `size` arrays in the Union-Find structure each require O(N) space. This is more space-efficient than the adjacency list approach if E is large.
**Pros:** Most efficient approach in terms of both time and space.; Optimal space complexity of O(N).; The Union-Find data structure is perfectly suited for this type of connectivity problem.
**Cons:** The Union-Find data structure might be less familiar to some than standard graph traversals.
### Explanation
The Union-Find data structure maintains a collection of disjoint sets. We can use it to efficiently group all connected nodes. The algorithm is as follows:
1. Initialize a Union-Find structure with `n` nodes, where each node is its own parent (i.e., `n` separate components). We also maintain an array to store the size of each component, initially 1 for all.
2. Iterate through each edge `[u, v]` in the `edges` array.
3. For each edge, call the `union` operation on nodes `u` and `v`. This operation finds the sets that `u` and `v` belong to and merges them if they are different. When merging, the size of the new combined set is updated.
4. After processing all edges, the DSU structure correctly represents the connected components. The nodes with the same root belong to the same component.
5. We can then find the size of each unique component. One way is to iterate through all nodes `i`, find their root `p = find(i)`, and use a map to store the size of the component rooted at `p`. The size is available from our size array at index `p`.
6. Once we have a list of all component sizes, we use the same combinatorial logic as the previous approach to calculate the total number of unreachable pairs.
```java
class UnionFind {
    private int[] parent;
    private int[] size;

    public UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]); // Path compression
    }

    public void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            // Union by size
            if (size[rootI] < size[rootJ]) {
                parent[rootI] = rootJ;
                size[rootJ] += size[rootI];
            } else {
                parent[rootJ] = rootI;
                size[rootI] += size[rootJ];
            }
        }
    }
    
    public int getSize(int i) {
        return size[find(i)];
    }
}

public long countUnreachablePairs(int n, int[][] edges) {
    UnionFind uf = new UnionFind(n);
    for (int[] edge : edges) {
        uf.union(edge[0], edge[1]);
    }

    long unreachablePairs = 0;
    long remainingNodes = n;
    boolean[] visitedRoots = new boolean[n];

    for (int i = 0; i < n; i++) {
        int root = uf.find(i);
        if (!visitedRoots[root]) {
            long componentSize = uf.getSize(root);
            unreachablePairs += componentSize * (remainingNodes - componentSize);
            remainingNodes -= componentSize;
            visitedRoots[root] = true;
        }
    }
    
    return unreachablePairs;
}
```
### Algorithm
- Create a `UnionFind` class with `find` and `union` operations, including optimizations like path compression and union by size/rank.
- Initialize a `UnionFind` instance for `n` nodes.
- Iterate through all `edges` and call `uf.union(u, v)` for each edge.
- Initialize `unreachable_pairs = 0` and `remaining_nodes = n`.
- Create a `visitedRoots` boolean array to avoid double-counting components.
- Iterate through each node `i` from `0` to `n-1`.
- Find the root of the component for node `i`.
- If this root has not been processed yet:
  - Get the size of this component from the `UnionFind` structure.
  - Add `component_size * (remaining_nodes - component_size)` to `unreachable_pairs`.
  - Subtract `component_size` from `remaining_nodes`.
  - Mark the root as visited.
- Return `unreachable_pairs`.

# Solutions
### Java

```java
class Solution {
private
  List<Integer>[] g;
private
  boolean[] vis;
public
  long countPairs(int n, int[][] edges) {
    g = new List[n];
    vis = new boolean[n];
    Arrays.setAll(g, i->new ArrayList<>());
    for (var e : edges) {
      int a = e[0], b = e[1];
      g[a].add(b);
      g[b].add(a);
    }
    long ans = 0, s = 0;
    for (int i = 0; i < n; ++i) {
      int t = dfs(i);
      ans += s * t;
      s += t;
    }
    return ans;
  }
private
  int dfs(int i) {
    if (vis[i]) {
      return 0;
    }
    vis[i] = true;
    int cnt = 1;
    for (int j : g[i]) {
      cnt += dfs(j);
    }
    return cnt;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long countPairs(int n, vector<vector<int>> &edges) {
    vector<int> g[n];
    for (auto &e : edges) {
      int a = e[0], b = e[1];
      g[a].push_back(b);
      g[b].push_back(a);
    }
    bool vis[n];
    memset(vis, 0, sizeof(vis));
    function<int(int)> dfs = [&](int i) {
      if (vis[i]) {
        return 0;
      }
      vis[i] = true;
      int cnt = 1;
      for (int j : g[i]) {
        cnt += dfs(j);
      }
      return cnt;
    };
    long long ans = 0, s = 0;
    for (int i = 0; i < n; ++i) {
      int t = dfs(i);
      ans += s * t;
      s += t;
    }
    return ans;
  }
};

```

### Python

```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

```