Union Find  with Size is good||284ms Beats 99.82%
Intuition\n Describe your first thoughts on how to solve this problem. \nA variant of UnionFind with component size is very suitible for solving this question.\
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nA variant of UnionFind with component size is very suitible for solving this question.\n\nFor comparison, a simple UnionFind without optimization with size is also implemented which is also fast & easily implemented.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Use UnionFind class with Size & components( count how many components it has)\n2. Construct 2 UnionFind objects Alice & Bob\n3. Process type 3 edges first\n4. Process type 1 and type 2 edges\n5. If the both of graphs for Alice and for Bob are connected, the answer is |edges|-edgesNeed, otherwise -1 \n# Why 2 passes? not 1 pass? not sorting?\nIn fact the solution is using Greedy algoirithm. The 1st loop processes type 3 edges; adding 1 type 3 edge has the effect of adding 1 edge in both Alice & Bob. Adding 1 type 1  edge just adding 1 edge in Alce, and adding 1 type 2 edge just adding 1 edge in Bob. \n\nThe problem is asking  to obtain the maximal number of edges one can remove. In other words, the minimal number edges are needed to build both Alice & Bob connective. So type 3 edges must be treated firsly. **1 pass solution will go wrong.**\n\nOther correct method is to use sort, but it will increase the time complexity. 2 passes solution has less time than any kind of sorting.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n+\\alpha(n)|edges|)$$ where $\\alpha(n)$  is the inverse Ackermann function which grows very slow & almost constant.\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$O(n)$\n# Code UnionFind with Size||284ms Beats 99.82%\n```\n// union find class with Size & components\nclass UnionFind {\n    vector<int> root, Size;\n    int components;\npublic:\n    //Constructor using initializer list\n    UnionFind(int n): root(n+1), Size(n+1,1), components(n){\n        iota(root.begin(), root.end(), 0);//[0,1,...,n]    \n    }\n    \n    int Find(int x) {//Path Compression O(alpha(n))\n        if (x==root[x]) \n            return x;\n        return root[x] = Find(root[x]);\n    }\n\n    bool Union(int x, int y) { //Union by Size O(alpha(n))   \n        x=Find(x), y=Find(y);\n        \n        if (x == y) return 0;\n        \n        if (Size[x] > Size[y]) {\n            Size[x] +=Size[y];\n            root[y] = x;\n        } \n        else {\n            Size[y] += Size[x];\n            root[x] = y;\n        }       \n        components--;\n        return 1;\n    }\n\n    bool isConnected() {\n        return components == 1;\n    }\n        \n};\n\nclass Solution {\npublic:\n    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {\n        UnionFind Alice(n), Bob(n);\n\n        int edgesNeed=0;\n        // Process type 3 edges first\n        for (vector<int>& e: edges) {\n            if (e[0]==3) {\n                edgesNeed+=(Alice.Union(e[1], e[2]) | Bob.Union(e[1], e[2]));\n            }\n        }\n        // Process type 1 and type 2 edges\n        for (vector<int>& e: edges){\n            if (e[0]==1) edgesNeed+=Alice.Union(e[1], e[2]);\n            else if (e[0]==2) edgesNeed+=Bob.Union(e[1], e[2]);\n        }\n\n        if (Alice.isConnected() && Bob.isConnected())\n            return edges.size()-edgesNeed;\n        return -1;\n    }\n};\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n\n```\n# C++ code using a simple UionFind class|| 289m Beats 99.82%\n```\nclass UnionFind { // simple version for UnionFind class\n    vector<int> root;\n    int components;\npublic:\n    UnionFind(int n):root(n+1), components(n) {\n        iota(root.begin(), root.end(), 0);\n    }\n\n    int Find(int x) {\n        if (x == root[x])\n            return x;\n        else\n            return root[x] = Find(root[x]);\n    }\n\n    bool Union(int x, int y) {//Without optimization\n        x= Find(x), y= Find(y);\n        if (x == y)\n            return 0;\n        else\n            root[y]=x;\n        components--;\n        return 1;\n    }\n\n\n    bool isConnected() {\n        return components == 1;\n    }\n        \n};\n\n```\nUnionFind is good for solving undirected graphical problem. The implemenations of it have several different versions, simple one, optimized by rank & optimized by size.\n1 easy application can be seen [1971. Find if Path Exists in Graph\n](https://leetcode.com/problems/find-if-path-exists-in-graph/solutions/5052126/union-find-is-good-vs-dfs-vs-bfs-193ms-beats-99-93/)\n[Please turn English subtitles if necessary]\n[https://youtu.be/B1GQlUN08lk?si=ty_sRVWJTrxO9CVG](https://youtu.be/B1GQlUN08lk?si=ty_sRVWJTrxO9CVG)
['Greedy', 'Union Find', 'Graph', 'C++']