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

August LeetCoding Challenge 19

Description

Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

Given a weighted undirected connected graph with n vertices numbered from 0 to n - 1, and an array edges where edges[i] = [ai, bi, weighti] represents a bidirectional and weighted edge between nodes ai and bi. A minimum spanning tree (MST) is a subset of the graph's edges that connects all vertices without cycles and with the minimum possible total edge weight.

Find all the critical and pseudo-critical edges in the given graph's minimum spanning tree (MST). An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. On the other hand, a pseudo-critical edge is that which can appear in some MSTs but not all.

Note that you can return the indices of the edges in any order.

Example 1:

Input: n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
Output: [[0,1],[2,3,4,5]]
Explanation: The figure above describes the graph.
The following figure shows all the possible MSTs:

Notice that the two edges 0 and 1 appear in all MSTs, therefore they are critical edges, so we return them in the first list of the output.
The edges 2, 3, 4, and 5 are only part of some MSTs, therefore they are considered pseudo-critical edges. We add them to the second list of the output.

Example 2:

Input: n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
Output: [[],[0,1,2,3]]
Explanation: We can observe that since all 4 edges have equal weight, choosing any 3 edges from the given 4 will yield an MST. Therefore all 4 edges are pseudo-critical.

Constraints:

• 2 <= n <= 100
• 1 <= edges.length <= min(200, n * (n - 1) / 2)
• edges[i].length == 3
• 0 <= ai < bi < n
• 1 <= weighti <= 1000
• All pairs (ai, bi) are distinct.

Solution

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 {
  int findMST(
    const vector<vector<int>>& edges,
    int n,
    int ignore,
    int mustHave
  ) {
    UnionSet us(n);

    int weight = 0;
    if(mustHave != -1) {
      us.merge(edges[mustHave][0], edges[mustHave][1]);
      weight += edges[mustHave][2];
    }

    for(int i = 0; i < edges.size(); ++i) {
      if(i == ignore) continue;
      if(us.find(edges[i][0]) == us.find(edges[i][1])) continue;
      us.merge(edges[i][0], edges[i][1]);
      weight += edges[i][2];
    }

    for(int i = 0; i < n; ++i) {
      if(us.find(i) != us.find(0)) {
        weight = INT_MAX;
        continue;
      }
    }

    return weight;
  }
public:
  vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
    vector<int> critical, pseudoCritical;

    for(int i = 0; i < edges.size(); ++i) {
      edges[i].push_back(i);
    }
    sort(edges.begin(), edges.end(), [](const vector<int> &a, const vector<int> &b) {
      return a[2] < b[2];
    });

    int MSTWeight = findMST(edges, n, -1, -1);

    for(int i = 0; i < edges.size(); ++i) {
      if(MSTWeight < findMST(edges, n, i, -1)) {
        critical.push_back(edges[i][3]);
      } else if(MSTWeight == findMST(edges, n, -1, i)) {
        pseudoCritical.push_back(edges[i][3]);
      }
    }

    return {critical, pseudoCritical};
  }
};

// Accepted
// 66/66 cases passed (160 ms)
// Your runtime beats 58.42 % of cpp submissions
// Your memory usage beats 86.58 % of cpp submissions (14.8 MB)