Count Unreachable Pairs of Nodes in an Undirected Graph LeetCode solution in C++

1
class Solution {
2
 public:
3
  typedef long long ll;
4
  void dfs(int node, unordered_map<int, vector<int>> &m, ll &cnt, vector<int> &vis) {
5
    vis[node] = 1;
6
    cnt++;
7
    for (auto &i : m[node]) {
8
      if (vis[i] == 0) dfs(i, m, cnt, vis);
9
    }
10
  }
11
  long long countPairs(int n, vector<vector<int>> &edges) {
12
    unordered_map<int, vector<int>> m; // making adjacency list
13
    for (int i = 0; i < edges.size(); i++) {
14
      m[edges[i][0]].push_back(edges[i][1]);
15
      m[edges[i][1]].push_back(edges[i][0]);
16
    }
17
    ll ans = ((ll)n * (n - 1)) / 2;
18
    vector<int> vis(n, 0);
19
    for (int i = 0; i < n; i++) {
20
      if (vis[i] == 0) { // as node is not visited, we find the no. of nodes in
21
                         // current component.
22
        ll cnt = 0;
23
        dfs(i, m, cnt, vis);
24
        ans -= (cnt * (cnt - 1)) / 2;
25
      }
26
    }
27
    return ans;
28
  }
29
};