Java Union Find Beginner friendly Full Explanation 17ms
Please upvote if u find useful\nCredits - A big thanks to @interviewrecipes and @akshay31verma\n\n\n  The idea here is to think that initially the graph is empt
**Please upvote if u find useful**\nCredits - A big thanks to @interviewrecipes and @akshay31verma\n\n\n*  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* As 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* Make all the components which you can reach from type 3 edges i.e traverserable for both Alice and Bob\n* Now using First go with alice and find if we can connect all the disconnected groups using the Alice edges.\n* And apply same for Bob.\n* Also in Union Find DS i have made var comp. to calculate the no of independent Component in the graph of Alice and Bob\n* we cal. comp. for both alice and bob\n* ***if the graph is fully traversible then we must no. comp. = 2 (coz 0 is indept. node)***\n\nMy Simple Java Code:\n```\npublic int maxNumEdgesToRemove(int n, int[][] edges) {\n\t\t int nboth=0,nalice=0,nbob=0;\n\t\t List<int[]> both=new Vector<>();\n\t\t List<int[]> bob=new Vector<>();\n\t\t List<int[]> alice=new Vector<>();\n\t\t \n\t\t for(int[] t:edges) {\n\t\t\t if(t[0]==3) {nboth++;both.add(t);}\n\t\t\t else if(t[0]==2) {nbob++;bob.add(t);}\n\t\t\t else {nalice++;alice.add(t);}\n\t\t }\n\t\t \n\t\t Dsu dsu_bob=new Dsu(n+1);\n\t\t Dsu dsu_alice=new Dsu(n+1);\n\t\tint ans=0;\n\t\tint edge=0;\n\t\tfor(int[] t:both) {\n\t\t\tif(dsu_alice.union(t[1], t[2])==false&&dsu_bob.union(t[1], t[2])==false)\n\t\t\t\tedge++;\n\t\t}\n\t\tans+=nboth-edge;\n\t\tedge=0;\n\t\tfor(int[] t:alice) {\n\t\t\tif(dsu_alice.union(t[1], t[2])==false)\n\t\t\t\tedge++;\n\t\t}\n\t\tans+=nalice-edge;\n\t\tedge=0;\n\t\tfor(int[] t:bob) {\n\t\t\tif(dsu_bob.union(t[1], t[2])==false)\n\t\t\t\tedge++;\n\t\t}\n\t\tans+=nbob-edge;\n\t\tif(dsu_alice.comp>2|| dsu_bob.comp>2) return -1;\n\t\treturn ans;\n\t }\n\t static class Dsu{\n\t\t int[] parent;\n\t\t int[] rank;\n\t\t int comp;\n\t\t Dsu(int N){\n\t\t\t parent=new int[N];\n\t\t\t rank=new int[N];\n\t\t\t Arrays.fill(parent, -1);\n\t\t\t this.comp=N;\n\t\t }\n\t\t int find(int x) {\n\t\t\t if(parent[x]==-1)return x;\n\t\t\t return parent[x]=find(parent[x]);\n\t\t }\n\t\t boolean union(int u,int v) {\n\t\t\t int p1=find(u);\n\t\t\t int p2=find(v);\n\t\t\t if(p1==p2)return true;\n\t\t\t \n\t\t\t if(rank[p1] >rank[p2])\n\t\t\t\t parent[p2]=p1;\n\t\t\t else if(rank[p2] >rank[p1])\n\t\t\t\t parent[p1]=p2;\n\t\t\t else {\n\t\t\t\t parent[p2]=p1;\n\t\t\t\t rank[p1]++;\n\t\t\t }\n\t\t\t comp--;\n\t\t\t return false;\n\t\t }\n\t }\n\n```\n\nTime: O(m), where m is the number of edges.\nMemory: O(n) \n**Please upvote if u find useful**
[]