1
class Solution {
2
 public:
3
  vector<int> Ar, Ap, Br, Bp; // alice and bob parent and rank arrays
4
  static bool cmp(vector<int> &a, vector<int> &b) {
5
    return a[0] > b[0];
6
  }
7
  // lets create the alice graph first
8
  // find function for finding the parent nodes
9
  int find1(int x) {
10
    if (x == Ap[x]) return x;
11
    return Ap[x] = find1(Ap[x]);
12
  }
13
  // if nodes are already connected return 1 else make the connection and return
14
  // 0
15
  bool union1(int x, int y) {
16
    int parX = find1(x);
17
    int parY = find1(y);
18
    if (parX == parY) return 1;
19
    if (Ar[parX] > Ar[parY]) {
20
      Ap[parY] = parX;
21
    } else if (Ar[parX] < Ar[parY]) {
22
      Ap[parX] = parY;
23
    } else {
24
      Ap[parY] = parX;
25
      Ar[parX]++;
26
    }
27
    return 0;
28
  }
29
  // same thing do for bob graph
30
  int find2(int x) {
31
    if (x == Bp[x]) return x;
32
    return Bp[x] = find2(Bp[x]);
33
  }
34

35
  bool union2(int x, int y) {
36
    int parX = find2(x);
37
    int parY = find2(y);
38
    if (parX == parY) return 1;
39
    if (Br[parX] > Br[parY]) {
40
      Bp[parY] = parX;
41
    } else if (Br[parX] < Br[parY]) {
42
      Bp[parX] = parY;
43
    } else {
44
      Bp[parY] = parX;
45
      Br[parX]++;
46
    }
47
    return 0;
48
  }
49

50
  int maxNumEdgesToRemove(int n, vector<vector<int>> &edges) {
51
    Ar.resize(n, 1);
52
    Ap.resize(n, 1);
53
    Br.resize(n, 1);
54
    Bp.resize(n, 1);
55

56
    for (int i = 0; i < n; i++) {
57
      Ap[i] = i;
58
      Bp[i] = i;
59
    }
60

61
    sort(edges.begin(), edges.end(), cmp);
62
    int ans = 0;
63
    // give priority to 3rd type of vertices
64
    for (auto a : edges) {
65
      if (a[0] != 3) continue;
66
      if (union1(a[1] - 1, a[2] - 1)) ans++;
67

68
      union2(a[1] - 1, a[2] - 1);
69
    }
70
    // now try the edges one by one and check if it the given nodes are already
71
    // connected in respective alice and bob graph or not
72
    for (auto a : edges) {
73
      if (a[0] == 3) continue;
74
      if (a[0] == 1) {
75
        if (union1(a[1] - 1, a[2] - 1)) ans++;
76
      }
77

78
      else {
79
        if (union2(a[1] - 1, a[2] - 1)) ans++;
80
      }
81
    }
82
    int cnt1 = 0, cnt2 = 0;
83
    for (int i = 0; i < n; i++) {
84
      if (Ap[i] == i) cnt1++;
85
      if (Bp[i] == i) cnt2++;
86
    }
87
    if (cnt1 > 1 | cnt2 > 1) return -1;
88

89
    return ans;
90
  }
91
};