Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- vector <int> d1;
- vector <int> d2;
- vector <int> s1;
- vector <int> s2;
- int parent(int x, vector <int> &dsu){
- if(x == dsu[x]){
- return x;
- }else{
- dsu[x] = parent(dsu[x], dsu);
- }
- return dsu[x];
- }
- int add(int a, int b, vector <int> &dsu, vector <int> &s){
- int p1 = parent(a, dsu);
- int p2 = parent(b, dsu);
- if(p1 == p2){
- return 1;
- }else{
- dsu[p1] = p2;
- s[p2] += s[p1];
- return 0;
- }
- }
- int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
- d1 = vector <int> (n+1, 0);
- d2 = vector <int> (n+1, 0);
- s1= vector <int>(n+1, 1);
- s2 = vector <int> (n+1, 1);
- for(int i =0 ; i <= n; ++i){
- d1[i] = i;
- d2[i] = i;
- }
- sort(edges.rbegin(), edges.rend());
- int ans = 0;
- for(auto &data: edges){
- if(data[0] == 3){
- ans += add(data[1], data[2], d1, s1);
- add(data[1], data[2], d2, s2);
- }else if(data[0] == 2){
- ans += add(data[1], data[2], d1, s1);
- }else if(data[0] == 1){
- ans += add(data[1], data[2], d2, s2);
- }
- }
- if(s1[parent(1, d1)] == n and s2[parent(1, d2)] == n){
- return ans;
- }else{
- return -1;
- }
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement