Golang Solution ||| O(N) ||| DFS (No union find) ||| A lot of Explanations ||| Clean code
Intuition\nCreate 3 graphs, find out the number of required edges for each graph and subtract them from the total number of edges.\n\n# Approach\n# Solution thr
# Intuition\nCreate 3 graphs, find out the number of required edges for each graph and subtract them from the total number of edges.\n\n# Approach\n# Solution through connectivity components\n\nThe idea is that **we create separate connectivity components only from edges of type 3**, and depending on their number we see how many edges we need for alice and for bob.\n\n# Let me give an example of some graph consisting only of edges of type 3 and explain how we can use it to find the answer.\n\nThis is an example of a graph that consists of only 3 edges.\n\n**It has four components of cohesion:**\n\n![image.png](https://assets.leetcode.com/users/images/f4f3c957-1424-4111-b1cb-6356a12f4c16_1719750850.1727984.png)\n\n# Recall that the minimum possible number of edges for a graph to be connected is n - 1, where n is the number of vertices.\n> Such a graph is called a tree.\n\n---\n\n\nTo make it possible for Alice, for example, to get from any vertex to any other vertex, **we need to connect all these connectivity components by a minimum number of edges.**\nThis number is equal to **4 - 1 = 3.**\nThe same logic applies to bean - **4 - 1 = 3.**\n\nExample:\n![image.png](https://assets.leetcode.com/users/images/c16bf456-a6a8-4967-bdd2-f7b1151088e3_1719751227.9210632.png)\n\n# That is, for both alice and bean, the number of good edges is equal to the number of connectivity components of the graph of general type - 1.**\n\n\n---\n\n# Let\'s talk about the number of good type 3 ribs. \n\nWe have, say, **m connectivity components.**\nTry to understand, I tried to make it clear). \uD83D\uDE02\n1. For each of the m components, the number of edges it needs for the component to be connected is equal to the number of its vertices - 1.\n2. In total, we have n vertices. And m components.\n3. The sum of all vertices of all components is n.\n4. If we sum up all the numbers of good edges for each component, we have n - m, because for each of the m components we subtract 1.\n\n# So the total number of good edges of type 3 is n - m.\n\n---\n# Thus, the total number of ribs needed:\n**Find the number of connectivity components of the graph consisting only of edges of type 3. Let it be m.**\n\n1. Number of good edges of type 3: n - m\n2. Number of good edges of type 1: m - 1\n3. Number of good edges of type 2: m - 1 (sane as 1)\n4. Total number of good edges: \n  (n - m) + (m - 1) + (m - 1) = \n  n - m + 2 * m - 2 = \n  n + m - 2\n# Total ans: nEdges - (n + m - 2)\n![Upvote Please.jpeg](https://assets.leetcode.com/users/images/3f99fa53-5322-42eb-afdd-fae1d28e5bf1_1719753338.5921237.jpeg)\n\n---\n\n\n# Let\'s deal with -1.\nWe return -1 **only if either Alice or Bob cannot pass the graph completely to any vertex.**\n\n**To check this**, we will create 2 graphs, one for Alice and one for Bob. \nFor alice we will add all edges whose type is either 1 or 3, and for bean either 2 or 3.\n\n**For them we** will also **find out the number of connectivity components. If it is not equal to 1**, then traversing the complete graph is impossible, **we return -1.**\n\n---\n# Code Explanation\n\n---\n```Golang []\ntype GraphType int\n\nconst (\n    AliceType GraphType  = 1\n    BobType GraphType    = 2\n    CommonType GraphType = 3\n)\n\n// Graph Struct\n\ntype Graph struct {\n    n int\n\n    g map[int][]int\n    graphType GraphType\n}\n```\n**The initialization methods are as follows:**\n```Golang []\nfunc NewGraph(graphType GraphType, n int, edges [][]int) *Graph {\n    newG := &Graph{\n        n: n,\n\n        g: make(map[int][]int),\n        graphType: graphType,\n    }\n\n    for _, edge := range edges {\n        newG.addEdge(edge)\n    }\n\n    return newG\n}\n\nfunc (g *Graph) addEdge(edge []int) {\n    edgeType, fromV, toV := edge[0], edge[1], edge[2]\n\n    switch g.graphType {\n    case AliceType:\n        if edgeType == 1 || edgeType == 3 {\n            g.g[fromV] = append(g.g[fromV], toV)\n            g.g[toV] = append(g.g[toV], fromV)\n        }\n    case BobType:\n        if edgeType == 2 || edgeType == 3 {\n            g.g[fromV] = append(g.g[fromV], toV)\n            g.g[toV] = append(g.g[toV], fromV)\n        }\n    case CommonType:\n        if edgeType == 3 {\n            g.g[fromV] = append(g.g[fromV], toV)\n            g.g[toV] = append(g.g[toV], fromV)\n        }\n    }\n}\n```\n\n**The remaining 2 methods are used to find the number of connectivity components.**\n# How do you find the number of components of a connectivity?\nIn the graph structure we will add the used field - an array of boolean\'s.\n```Golang []\ntype Graph struct {\n    //....\n\n    used []bool\n}\n```\nIn a special method, where we will get the number of components of links, **we will try to call DFS from all vertices from 1 to n.**\n\n**If we succeed** *(i.e., the vertex has not yet been marked as used)*, **we increment the counter and start DFS from this vertex.** \n\n```Golang []\nfunc (g *Graph) GetComponentsCount() int {\n    componentsCount := 0\n    for startV := 1; startV <= g.n; startV++ {\n        if !g.used[startV] {\n            g.dfs(startV)\n            componentsCount++\n        }\n    }\n\n    return componentsCount\n}\n```\n**DFS is super standard, absolutely nothing new.**\n```Golang []\nfunc (g *Graph) dfs(v int) {\n    if g.used[v] {\n        return\n    }\n    g.used[v] = true\n    for _, nextV := range g.g[v] {\n        g.dfs(nextV)\n    }\n}\n```\n\n# Because of the structure, it is now very easy for us to start a graph and count the number of good and necessary edges according to our solution.\n\n**The main method itself looks like this.** *I didn\'t comment the code, just made the names of the variables.*\n\n```Golang []\nfunc maxNumEdgesToRemove(n int, edges [][]int) int {\n    aliceG := NewGraph(AliceType, n, edges)\n    bobG := NewGraph(BobType, n, edges)\n\n\n    aliceCompopentsCount := aliceG.GetComponentsCount()\n    bobCompopentsCount := bobG.GetComponentsCount()\n\n    if aliceCompopentsCount != 1 || bobCompopentsCount != 1 {\n        return -1\n    }\n\n    commonG := NewGraph(CommonType, n, edges)\n    commonCompopentsCount := commonG.GetComponentsCount()\n\n    goodCommodEdges := n - commonCompopentsCount\n    goodAliceEdges := commonCompopentsCount - 1\n    goodBobEdges := goodAliceEdges // (commonCompopentsCount - 1)\n    \n    sumOfGoodEdges := goodCommodEdges + goodAliceEdges + goodBobEdges\n    return len(edges) - sumOfGoodEdges\n}\n```\n![Upvote Please.jpeg](https://assets.leetcode.com/users/images/3f99fa53-5322-42eb-afdd-fae1d28e5bf1_1719753338.5921237.jpeg)\n\n\n# Complexity\n**- Time complexity:**\nThe graph creation itself takes at most $$O(N)$$.\nThe sum of execution time of the GetComponentsCount() method is $$O(N)$$, because we pass strictly over N vertices. total. \nCalculation of all variables in the main is $$O(1)$$.\n\n**Total time complexity -** $$O(N)$$\n\n# Code\n```\nfunc maxNumEdgesToRemove(n int, edges [][]int) int {\n    aliceG := NewGraph(AliceType, n, edges)\n    bobG := NewGraph(BobType, n, edges)\n\n\n    aliceCompopentsCount := aliceG.GetComponentsCount()\n    bobCompopentsCount := bobG.GetComponentsCount()\n\n    if aliceCompopentsCount != 1 || bobCompopentsCount != 1 {\n        return -1\n    }\n\n    commonG := NewGraph(CommonType, n, edges)\n    commonCompopentsCount := commonG.GetComponentsCount()\n\n    goodCommodEdges := n - commonCompopentsCount\n    goodAliceEdges := commonCompopentsCount - 1\n    goodBobEdges := goodAliceEdges // (commonCompopentsCount - 1)\n    \n    sumOfGoodEdges := goodCommodEdges + goodAliceEdges + goodBobEdges\n    return len(edges) - sumOfGoodEdges\n}\n\n// ________________\n// Graph\n// ________________\n\ntype GraphType int\n\nconst (\n    AliceType GraphType  = 1\n    BobType GraphType    = 2\n    CommonType GraphType = 3\n)\n\n// Graph Struct\n\ntype Graph struct {\n    n int\n\n    g map[int][]int\n    graphType GraphType\n\n    used []bool\n}\n\n// Initializators\n\nfunc NewGraph(graphType GraphType, n int, edges [][]int) *Graph {\n    newG := &Graph{\n        n: n,\n\n        g: make(map[int][]int),\n        graphType: graphType,\n\n        used: make([]bool, n + 1),\n    }\n\n    for _, edge := range edges {\n        newG.addEdge(edge)\n    }\n\n    return newG\n}\n\nfunc (g *Graph) addEdge(edge []int) {\n    edgeType, fromV, toV := edge[0], edge[1], edge[2]\n\n    switch g.graphType {\n    case AliceType:\n        if edgeType == 1 || edgeType == 3 {\n            g.g[fromV] = append(g.g[fromV], toV)\n            g.g[toV] = append(g.g[toV], fromV)\n        }\n    case BobType:\n        if edgeType == 2 || edgeType == 3 {\n            g.g[fromV] = append(g.g[fromV], toV)\n            g.g[toV] = append(g.g[toV], fromV)\n        }\n    case CommonType:\n        if edgeType == 3 {\n            g.g[fromV] = append(g.g[fromV], toV)\n            g.g[toV] = append(g.g[toV], fromV)\n        }\n    }\n}\n\n// ____________\n// DFS\n// ____________\n\nfunc (g *Graph) GetComponentsCount() int {\n    componentsCount := 0\n    for startV := 1; startV <= g.n; startV++ {\n        if !g.used[startV] {\n            g.dfs(startV)\n            componentsCount++\n        }\n    }\n\n    return componentsCount\n}\n\nfunc (g *Graph) dfs(v int) {\n    if g.used[v] {\n        return\n    }\n    g.used[v] = true\n    for _, nextV := range g.g[v] {\n        g.dfs(nextV)\n    }\n}\n\n\n```\n\n![Upvote Please.jpeg](https://assets.leetcode.com/users/images/3f99fa53-5322-42eb-afdd-fae1d28e5bf1_1719753338.5921237.jpeg)
['Depth-First Search', 'Graph', 'Design', 'Go']