Problem statement

https://leetcode.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/

Solution

The idea is the following: what will be in the end if we consider graphs for Alice and Bob are two trees, so with fixed number of edges: n-1 in each. If we want to minimize number of removed edges, it means, that in the end we need to have as few edges in total as possible: it means we want as many double edges as possible. So the algorithm is following:

  1. Check that graphs for Alice and Bob are connected, if not return -1
  2. Conctruct graph for type 3 edges: we want to keep as much edges of this type as possible and then for all ways to extend it to trees for Alice and Bob they will have the same number of nodes. So, we look at graph, constructed with type 3 edges and we need to remove all cycles in it. Actually it only depends on number of connected components and number of edges.
  3. In the end after some simplifications, answer is len(edges) - n + 2 - comps

Complexity

Time and space complexity is O(E+V)

Code

class Solution:
    def maxNumEdgesToRemove(self, n, edges):
        G = [defaultdict(set) for _ in range(3)]
        neibs = {1:[1], 2:[2], 3:[1, 2, 3]}
        
        for i, u, v in edges:
            for j in neibs[i]:
                G[j-1][u].add(v)
                G[j-1][v].add(u)

        def dfs(node, ind):
            V.add(node)
            for neib in G[ind][node]:
                if neib not in V: dfs(neib, ind)

        V = set()
        dfs(1, 0)
        if len(V) != n: return -1
        V = set()
        dfs(1, 1)
        if len(V) != n: return -1
        V = set()
        comps = 0

        for i in range(1, n+1):
            if i not in V:
                dfs(i, 2)
                comps += 1

        return len(edges) - n + 2 - comps

Remark

There is alternative way using DSU: we start to build graph, first adding edges of type 3 then adding all other edges, keeping two different DSU for Alice and for Bob, complexity will be the same.