1
class Solution {
2
  public int maxNumEdgesToRemove(int n, int[][] edges) {
3
    Arrays.sort(
4
        edges,
5
        (a, b) -> {
6
          return b[0] - a[0];
7
        }); // giving the priority to third type of edge or the edge which Bob and Alice both can
8
    // access
9

10
    // 1-based indexing of nodes
11
    int[] parentAlice = new int[n + 1]; // Graph 1 for Alice connectedness
12
    int[] parentBob = new int[n + 1]; // Graph 2 for Bob connectedness
13

14
    for (int i = 0;
15
        i < n + 1;
16
        i++) { // every node is pointing to itself, at first no connection is considered all sets
17
      // are independent(no dependency)
18
      parentAlice[i] = i;
19
      parentBob[i] = i;
20
    }
21

22
    // number of merged unique node for Alice and Bob that are required to maintain the
23
    // connectedness of Alice and Bob graph nodes//intialised with one because merging happens in
24
    // pair
25
    int mergeAlice = 1;
26
    int mergeBob = 1;
27

28
    // number of cyclic or the non dependent node, that are not required for the connectedness of
29
    // Alice and Bob nodes
30
    int removeEdge = 0;
31

32
    for (int[] edge : edges) {
33
      int cat =
34
          edge[
35
              0]; // category of edge 1)edge Alice can only access 2)edge Bob can only access 3)edge
36
      // both Alice and Bob can access
37
      int u = edge[1];
38
      int v = edge[2];
39

40
      if (cat == 3) { // edge both Alice and Bob an access
41

42
        // creating dependency of nodes in graph 1 and 2
43
        boolean tempAlice = union(u, v, parentAlice);
44
        boolean tempBob = union(u, v, parentBob);
45

46
        if (tempAlice == true) mergeAlice += 1;
47

48
        if (tempBob == true) mergeBob += 1;
49

50
        if (tempAlice == false
51
            && tempBob
52
                == false) // retundant or the cyclic non-dependent edge//both Alice and Bob don't
53
          // rquire it connection is already there between these pair of nodes
54
          removeEdge += 1;
55
      } else if (cat == 2) { // edge Bob can only access
56

57
        // creating dependency of nodes in graph 2
58
        boolean tempBob = union(u, v, parentBob);
59

60
        if (tempBob == true) mergeBob += 1;
61
        else // no merging of set is done, that means that this edge is not required because it will
62
          // form cycle or the dependency
63
          removeEdge += 1;
64
      } else { // edge Alice can only access
65

66
        // creating dependency of nodes in graph 1
67
        boolean tempAlice = union(u, v, parentAlice);
68

69
        if (tempAlice == true) mergeAlice += 1;
70
        else // no merging of set is done, that means that this edge is not required because it will
71
          // form cycle or the dependency
72
          removeEdge += 1;
73
      }
74
    }
75
    if (mergeAlice != n
76
        || mergeBob != n) // all node are not connected, connectedness is not maintained
77
    return -1;
78
    return removeEdge; // number of edge removed by maintaining the connectedness
79
  }
80

81
  public int find(int x, int[] parent) {
82
    if (parent[x] == x) // when we found the absolute root or the leader of the set
83
    return x;
84

85
    int temp = find(parent[x], parent);
86

87
    parent[x] =
88
        temp; // Path Compression//child pointing to the absolute root or the leader of the set,
89
    // while backtracking
90

91
    return temp; // returning the absolute root
92
  }
93

94
  public boolean union(int x, int y, int[] parent) {
95
    int lx = find(x, parent); // leader of set x or the absolute root
96
    int ly = find(y, parent); // leader of set y or the absolute root
97

98
    if (lx != ly) { // belong to different set merging
99

100
      // Rank Compression is not done, but you can do it
101
      parent[lx] = ly;
102

103
      return true; // union done, dependency created
104
    } else return false; // no union done cycle is due to this edge
105
  } // Please do Upvote, it helps a lot
106
}