Simple solution using dsu in cpp
Data structure used : Dis joint set union.\nAlgorithm used : Cycle in undirected graph using dis joint set data structure and check if a graph is connected usin
Data structure used : Dis joint set union.\nAlgorithm used : Cycle in undirected graph using dis joint set data structure and check if a graph is connected using dis joint set data structure.\nTime complexity : O(n)\nSpace complexity : O(n)\n\nIn this problem we need to remove maximum number of edges so that our graph remains fully traversed by both Alice and Bob individually or tell that it is impossible to traverse graph completely.\n\nEdges are of three type here:\n\nType 1: Can be traversed by Alice only.\nType 2: Can be traversed by Bob only.\nType 3: Can by traversed by both Alice and Bob.\n\nWe can think greedly here that we should use maximum Type 3 edges, so that we can need to use less of Type 1 and Type 2 edges. So first we try to use Type 3 for both and then, Type 1 and Type 2 individually.\n\nWe will use the concept of cycle formation, we add an edge only when it is connecting two different components\nof graph otherwise increase our counter variable (for count of edge deletion).\n\nAt the end we check for both Alice and Bob if graph is fully connected for them, this can be done easily by\nfinding if all vertices have same parent in dis joint set structure.\n\nC++ implementation:\n\n```\nint find_set(int parent[],int v)\n{\n    if(v == parent[v])\n        return v;\n    return parent[v] = find_set(parent,parent[v]);\n}\nvoid union_set(int parent[],int a,int b)\n{\n    a = find_set(parent,a);\n    b = find_set(parent,b);\n    if(a != b)\n        parent[b] = a;\n}\nclass Solution {\npublic:\n    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {\n        int parent1[n+1];\n        int parent2[n+1];\n        for(int i=1;i<=n;i++)\n            parent1[i] = parent2[i] = i;\n        int ans = 0;\n        for(int i=0;i<edges.size();i++)\n        {\n            if(edges[i][0] == 3)\n            {\n                int t1 = find_set(parent1,edges[i][1]);\n                int t2 = find_set(parent1,edges[i][2]);\n                if(t1 != t2)\n                {\n                    union_set(parent1,edges[i][2],edges[i][1]);\n                    union_set(parent2,edges[i][2],edges[i][1]);\n                }\n                else\n                    ans++;\n            }\n        }\n        for(int i=0;i<edges.size();i++)\n        {\n            if(edges[i][0] == 1)\n            {\n                int t1 = find_set(parent1,edges[i][1]);\n                int t2 = find_set(parent1,edges[i][2]);\n                if(t1 != t2)\n                {\n                    union_set(parent1,edges[i][2],edges[i][1]);\n                }\n                else\n                    ans++;\n            }\n            else if(edges[i][0] == 2)\n            {\n                int t1 = find_set(parent2,edges[i][1]);\n                int t2 = find_set(parent2,edges[i][2]);\n                if(t1 != t2)\n                {\n                    union_set(parent2,edges[i][2],edges[i][1]);\n                }\n                else\n                    ans++;\n            }\n        }\n        int par1 = find_set(parent1,1);\n        for(int i=1;i<=n;i++)\n        {\n            int t = find_set(parent1,i);\n            if(t != par1)\n                return -1;\n        }\n        int par2 = find_set(parent2,1);\n        for(int i=1;i<=n;i++)\n        {\n            int t = find_set(parent2,i);\n            if(t != par2)\n                return -1;\n        }\n        return ans;\n    }\n};\n```
['C++']