C++ DFS + connected components
Intuition\nOnly scenario when answer is not possible is when either alice or bob are unable to visit any vertex from any source vertex with all edges present. E
# Intuition\nOnly scenario when answer is not possible is when either alice or bob are unable to visit any vertex from any source vertex with all edges present. Else, answer is always possible. To find the maximum edges that can be removed, traverse the graph with only edges of type 3 as much as possible. This will leave C disconnected components in graph, which can be connected with 2*(C-1) edges of type 1 and 2 each. \n\n# Approach\nMake 3 graphs : one which alice can traverse, one for bob and one with only type 3 edges (we can manage with a single graph too if needed). First check if the alice and bob graphs are connected using dfs. If not, then answer is not possible. \n\nThen, traverse the graph with type 3 edges using dfs only to make components of graph (each component needs to have only sz-1 edges if size of that component is sz, so we can remove rest of edges from each component). Now we can connect these C components with 2*(C-1) edges and can remove the rest of edges.\n\n# Complexity\n- Time complexity: O(V+E)\n\n- Space complexity: O(V+E)\n\n# Code\n```\nclass Solution {\npublic:\n    \n    void dfs(int node, vector<int>& vis, vector<vector<int>>& graph, \n            int& sz, int& curedges){\n        vis[node]=1;\n        sz++;\n        curedges+=graph[node].size();\n        for(auto& g:graph[node]){\n            if(!vis[g]){\n                dfs(g,vis,graph,sz,curedges);\n            }\n        }\n    }\n    \n    bool checkPossible(vector<vector<int>>& graph){\n        int n=graph.size()-1;\n        vector<int> vis(n+1,0);\n        int sz=0,curedges=0;\n        dfs(1,vis,graph,sz,curedges);\n        for(int i=1;i<=n;++i){\n            if(!vis[i]) return false;\n        }\n        return true;\n    }\n    \n    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {\n        vector<vector<int>> graph(n+1),alice(n+1),bob(n+1);\n        int total=edges.size(),type3=0;\n        for(auto& e:edges){\n            if(e[0]==3){\n                graph[e[1]].push_back(e[2]);\n                graph[e[2]].push_back(e[1]);\n                alice[e[1]].push_back(e[2]);\n                alice[e[2]].push_back(e[1]);\n                bob[e[1]].push_back(e[2]);\n                bob[e[2]].push_back(e[1]);\n                type3++;\n            }\n            if(e[0]==1){\n                alice[e[1]].push_back(e[2]);\n                alice[e[2]].push_back(e[1]);\n            }\n            if(e[0]==2){\n                bob[e[1]].push_back(e[2]);\n                bob[e[2]].push_back(e[1]);\n            }\n        }\n        if(!checkPossible(alice)) return -1;\n        if(!checkPossible(bob)) return -1;\n        total=total-type3;\n        int components=0,ans=0;\n        vector<int> vis(n+1,0);\n        for(int i=1;i<=n;++i){\n            if(!vis[i]){\n                components++;\n                int sz=0,curedges=0;\n                dfs(i,vis,graph,sz,curedges);\n                curedges/=2;\n                ans+=curedges-(sz-1);\n            }\n        }\n        total-=2*(components-1);\n        ans+=total;\n        return ans;\n    }\n};\n```
['Depth-First Search', 'Graph', 'Recursion', 'C++']