A solution WITHOUT union-find. Just do at most 3 times of DFS/BFS
Almost all the solutions posted in Discuss are Union-Find solution. So I am providing a different solution without union-find here: Just do at most 3 times of g
Almost all the solutions posted in Discuss are Union-Find solution. So I am providing a different solution without union-find here: Just do at most 3 times of graph traversal.\n1. First travel the graph by using only edge type 1 and type 3. If it can\'t visit all the nodes, then it means Alice can\'t visit all nodes. Return -1.\n2. Then travel the graph by using only edge type 2 and type 3. If it can\'t visit all the nodes, then it means Bob can\'t visit all nodes. Return -1.\n3. Finally travel the graph by using only edge type 3 and count the number of connected component, say x.  Then the result is **edges.length - (n -1 + x -1)**.\n```\nclass Solution {\n    public int maxNumEdgesToRemove(int n, int[][] edges) {\n        ArrayList<Integer>[] als1=new ArrayList[n], als2=new ArrayList[n], als3=new ArrayList[n];\n        for(int i=0;i<n;++i){\n            als1[i]=new ArrayList();\n            als2[i]=new ArrayList();\n            als3[i]=new ArrayList();\n        }\n        for(int[] e : edges){\n            if(e[0]==1){\n                als1[e[1]-1].add(e[2]-1);\n                als1[e[2]-1].add(e[1]-1);\n            }else if(e[0]==2){\n                als2[e[1]-1].add(e[2]-1);\n                als2[e[2]-1].add(e[1]-1);\n            }else{\n                als3[e[1]-1].add(e[2]-1);\n                als3[e[2]-1].add(e[1]-1);\n            }\n        }\n        int[] kk=new int[1];\n        check(als1,als3,new boolean[n],0,kk);\n        if(kk[0]!=n)return -1;\n        kk[0]=0;\n        check(als2,als3,new boolean[n],0,kk);\n        if(kk[0]!=n)return -1;\n        boolean[] f=new boolean[n];\n        int count=0;\n        for(int i=0;i<n;++i){\n            if(!f[i]){\n                ++count;\n                todo(als3,f,i);\n            }\n        }\n        return edges.length - (n-1+(count-1));\n    }\n    \n    private void todo(ArrayList<Integer>[] als, boolean[] f, int st){\n        f[st]=true;\n        for(int n : als[st]){\n            if(!f[n])todo(als, f, n);\n        }\n    }\n    \n    private void check(ArrayList<Integer>[] als1, ArrayList<Integer>[] als2, boolean[] f, int st, int[] kk){\n        f[st]=true;\n        ++kk[0];\n        for(int n : als1[st]){\n            if(!f[n])check(als1, als2, f, n, kk);\n        }\n        for(int n : als2[st]){\n            if(!f[n])check(als1, als2, f, n, kk);\n        }\n    }\n}\n```
[]