October Challenge 2019: Faulty System

Official Editorial https://discuss.codechef.com/t/cnnct2-editorial/40191

Please consider this problem: Please construct two trees on each graph so that the number of edges which appears in both trees as many as possible. This problem is the same as the original problem. The answer can be written as 2(N-1)-(the number of common edges).

Subset of edges which doesn't form any cycle on each graph forms a matroid, say M1 on the first graph and say M2 on the second graph. In this problem, we should find the intersection of M1 and M2, which called a matroid intersection. We can find the maximum subset of edges contained in both M1 and M2 by using a generic algorithm. The algorithm for finding the maximum subset on matroid intersection is described in Combinatorial Optimization, so I won't explain it here.