🔥 LeetCode Editorial-Style Solution 🔥 | Union-Find | DSU | Beats 100% 🚀
🧠 Intuition
The problem requires determining the maximum number of edges that can be removed while keeping both Alice and Bob's graphs fully connected.
Union-Fi
# 🧠 Intuition
- The problem requires determining the maximum number of edges that can be removed while keeping both Alice and Bob's graphs fully connected.
- Union-Find (Disjoint Set Union - DSU) is ideal for this problem to efficiently track components.

# 🔍 Approach
1️⃣ Union-Find Data Structure
- Parent Array: Helps in finding the root of a node.
- Size Array: Maintains the size of each connected component.
2️⃣ Process Edges in Decreasing Order of Type
- Type 3 (Common Edges): Used by both Alice & Bob (Process first to maximize sharing).
- Type 1 (Alice-Only Edges): Used only for Alice.
- Type 2 (Bob-Only Edges): Used only for Bob.
3️⃣ Count Edges Used & Remaining Components
- If Alice and Bob each form a single component, return the edges removed.
- Otherwise, return -1 (Impossible to connect both graphs).
- 
# ⏳ Complexity Analysis
- Sorting Edges: O(E log E)

- Union-Find Operations: O(α(N)) ~ O(1) (Inverse Ackermann Function)

- Total Complexity: O(E log E + E) ≈ O(E log E) (Efficient for large inputs)

- Space Complexity: O(N) (For DSU arrays)



# 🔥 LeetCode Code | DSU | 🚀 Optimized
```cpp []
class disjoint{
    public:
            vector<int> size,parent;

            disjoint(int n){
                size.resize(n+1,1);
                parent.resize(n+1);
                for(int i=1;i<=n;i++){
                    parent[i]=i;
                }
            }

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

            void uNion(int u,int v){
                int ulp_u=find(u);
                int ulp_v=find(v);
                if(ulp_v==ulp_u){
                    return ;
                }

                if(size[ulp_u]<=size[ulp_v]){
                    parent[ulp_u]=ulp_v;
                    size[ulp_v]+=size[ulp_u];
                }
                else{
                    parent[ulp_v]=ulp_u;
                    size[ulp_u]+=size[ulp_v];
                }
            }
};

class Solution {
public:
    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
        int count=0;
        disjoint dsA(n);
        disjoint dsB(n);
        int componentA=n;
        int componentB=n;
        sort(edges.begin(),edges.end(),[](const vector<int>& a,const vector<int>& b){return a[0]>b[0];});
        
        for(int i=0;i<edges.size();i++){
            int e=edges[i][0];
            int u=edges[i][1];
            int v=edges[i][2];
            if(e==3){
                int ult_1=dsA.find(edges[i][1]);
                int ult_2=dsA.find(edges[i][2]);
                int ult_3=dsB.find(edges[i][1]);
                int ult_4=dsB.find(edges[i][2]);
                if(ult_1!=ult_2 && ult_3!=ult_4){
                    componentA--;
                    count++;
                    componentB--;
                    dsA.uNion(ult_1,ult_2);
                    dsB.uNion(ult_1,ult_2);
                }
            }
            else if(e==1){
                int ult_1=dsA.find(edges[i][1]);
                int ult_2=dsA.find(edges[i][2]);
                if(ult_1!=ult_2){
                    count++;
                    componentA--;
                    dsA.uNion(ult_1,ult_2);
                }
            }
            else{
            // e==2
                int ult_1=dsB.find(edges[i][1]);
                int ult_2=dsB.find(edges[i][2]);
                if(ult_1!=ult_2){
                    count++;
                    componentB--;
                    dsB.uNion(ult_1,ult_2);
                }
            }
        }

        if(componentA==1 &&  componentB==1){
            return edges.size()-count;
        }   

        return -1;
        
    }
};
```
['C++']