Today I have done leetcode's March LeetCoding Challenge with cpp.

March LeetCoding Challenge 25

Description

Count Unreachable Pairs of Nodes in an Undirected Graph

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:

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:

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.

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
struct UnionSet {
  vector<int> parent;
public:
  UnionSet(int size): parent(size) {
    for(int i = 0; i < size; ++i) {
      parent[i] = i;
    }
  }

  int find(int x) {
    if(parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
  }

  void merge(int x, int y) {
    x = find(x);
    y = find(y);
    parent[x] = y;
  }
};
class Solution {
public:
  long long countPairs(int n, vector<vector<int>>& edges) {
    UnionSet us(n);
    for(const auto &edge : edges) {
      us.merge(edge[0], edge[1]);
    }

    map<int, int> group;
    for(int i = 0; i < n; ++i) {
      group[us.find(i)] += 1;
    }

    vector<int> counts;
    counts.reserve(group.size());
    for(const auto &[_, count] : group) {
      counts.push_back(count);
    }
    long long answer = 0;
    for(int i = 1; i < counts.size(); ++i) {
      answer += 1LL * counts[i] * counts[i - 1];
      counts[i] += counts[i - 1];
    }

    return answer;
  }
};

// Accepted
// 66/66 cases passed (497 ms)
// Your runtime beats 95.88 % of cpp submissions
// Your memory usage beats 91.62 % of cpp submissions (150.5 MB)