Count Unreachable Pairs of Nodes in an Undirected Graph LeetCode solution in Java

1
class Solution {
2
  public long countPairs(int n, int[][] edges) {
3
    // Building Graph
4
    ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
5
    for (int i = 0; i < n; i++) graph.add(new ArrayList<Integer>());
6
    for (int arr[] : edges) {
7
      graph.get(arr[0]).add(arr[1]);
8
      graph.get(arr[1]).add(arr[0]);
9
    }
10
    boolean visited[] = new boolean[n];
11
    long res = 0;
12
    int prev = 0;
13
    int count[] = {0};
14
    for (int i = 0;
15
        i < graph.size();
16
        i++) { // Running for loop on all connected components of graph
17
      if (visited[i] == true)
18
        continue; // if the node is alredy reached by any of other vertex then we don't need to
19
      // terverse it again
20
      dfs(graph, i, visited, count);
21
      long a = n - count[0]; // (total - current count)
22
      long b = count[0] - prev; // (current count - prev )
23
      prev = count[0]; // Now Store count to prev
24
      res += (a * b);
25
    }
26
    return res;
27
  }
28

29
  void dfs(ArrayList<ArrayList<Integer>> graph, int v, boolean vis[], int count[]) {
30
    vis[v] = true;
31
    count[0]++; // for counting connected nodes
32
    for (int child : graph.get(v)) {
33
      if (!vis[child]) {
34
        dfs(graph, child, vis, count);
35
      }
36
    }
37
  }
38
}