[C++ / Java] Textbook Union-Find Data Structure, Code with Explanation and comments
The idea here is to think that initially the graph is empty and now we want to add the edges into the graph such that graph is connected.\n\nUnion-Find is an ea
The idea here is to think that initially the graph is empty and now we want to add the edges into the graph such that graph is connected.\n\nUnion-Find is an easiest way to solve such problem where we start with all nodes in separate components and merge the nodes as we add edges into the graph.\n\nAs some edges are available to only Bob while some are available only to Alice, we will have two different union find objects to take care of their own traversability.\n\nKey thing to remember is that we should prioritize type 3 edges over type 1 and 2 because they help both of them at the same time.\n**C++**\n```\n/* You can simply plug in this class any many different codes. This class is a generic implementation of union-find. */\nclass UnionFind {\n    vector<int> component;\n    int distinctComponents;\npublic:\n    /*\n     *   Initially all \'n\' nodes are in different components.\n     *   e.g. component[2] = 2 i.e. node 2 belong to component 2.\n     */\n    UnionFind(int n) {\n\t    distinctComponents = n;\n        for (int i=0; i<=n; i++) {\n            component.push_back(i);\n        }\n    }\n    \n    /*\n     *   Returns true when two nodes \'a\' and \'b\' are initially in different\n     *   components. Otherwise returns false.\n     */\n    bool unite(int a, int b) {       \n        if (findComponent(a) == findComponent(b)) {\n            return false;\n        }\n        component[findComponent(a)] = b;\n        distinctComponents--;\n        return true;\n    }\n    \n    /*\n     *   Returns what component does the node \'a\' belong to.\n     */\n    int findComponent(int a) {\n        if (component[a] != a) {\n            component[a] = findComponent(component[a]);\n        }\n        return component[a];\n    }\n    \n    /*\n     *   Are all nodes united into a single component?\n     */\n    bool united() {\n        return distinctComponents == 1;\n    }\n};\n\n\n\n// ----------------- Actual Solution --------------\nclass Solution {\n    \npublic:\n    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {\n        // Sort edges by their type such that all type 3 edges will be at the beginning.\n        sort(edges.begin(), edges.end(), [] (vector<int> &a, vector<int> &b) { return a[0] > b[0]; });\n        \n        int edgesAdded = 0; // Stores the number of edges added to the initial empty graph.\n        \n        UnionFind bob(n), alice(n); // Track whether bob and alice can traverse the entire graph,\n                                    // are there still more than one distinct components, etc.\n        \n        for (auto &edge: edges) { // For each edge -\n            int type = edge[0], one = edge[1], two = edge[2];\n            switch(type) {\n                case 3:\n                    edgesAdded += (bob.unite(one, two) | alice.unite(one, two));\n                    break;\n                case 2:\n                    edgesAdded += bob.unite(one, two);\n                    break;\n                case 1:\n                    edgesAdded += alice.unite(one, two);\n                    break;\n            }\n        }\n        \n        return (bob.united() && alice.united()) ? (edges.size()-edgesAdded) : -1; // Yay, solved.\n    }\n};\n```\n\n**Java** (Credits to @binlei)\n```\nclass Solution {\n    public int maxNumEdgesToRemove(int n, int[][] edges) {\n        Arrays.sort(edges, (a, b) -> b[0] - a[0]);\n        \n        int edgeAdd = 0;\n        \n        UnionFind alice = new UnionFind(n);\n        UnionFind bob = new UnionFind(n);\n        \n        for (int[] edge : edges) {\n            int type = edge[0];\n            int a = edge[1];\n            int b = edge[2];\n            \n            switch (type) {\n                case 3:\n                    if (alice.unite(a, b) | bob.unite(a, b)) {\n                        edgeAdd++;\n                    }\n                    break;\n                case 2:\n                    if (bob.unite(a, b)) {\n                        edgeAdd++;\n                    }\n                    break;\n                case 1:\n                    if (alice.unite(a, b)) {\n                        edgeAdd++;\n                    } \n                    break;\n            }\n        }\n        \n        return (alice.united() && bob.united()) ? edges.length - edgeAdd : -1;\n    }\n    \n    private class UnionFind {\n        int[] component;\n        int distinctComponents;\n        \n        public UnionFind(int n) {\n            component = new int[n+1];\n            for (int i = 0; i <= n; i++) {\n                component[i] = i;\n            }\n            distinctComponents = n;\n        }\n        // unite. For example, if previously we have component {0, 4, 4, 4, 4, 6, 7, 7}, then invoke this method with a=1, b=5, then after invoke, {0, 4, 4, 4, 5, 7, 7, 7}\n        private boolean unite(int a, int b) {\n            if (findComponent(a) != findComponent(b)) {\n                component[findComponent(a)] = b;\n                distinctComponents--;\n                return true;\n            }\n            \n            return false;\n        }\n        \n        // find and change component\n        // for example, if previously we have component:{0, 2, 3, 4, 4, 6, 7, 7}, then after invoke this method with a=1, the component become {0, 4, 4, 4, 4, 6, 7, 7}\n        private int findComponent(int a) {\n            if (component[a] != a) {\n                component[a] = findComponent(component[a]);\n            }\n            return component[a];\n        }\n        \n        private boolean united() {\n            return distinctComponents == 1;\n        }\n        \n    }\n}\n```
[]