Official Analysis (C++)

Explanation

The key idea is to focus on the connected components of both graphs. Any edge in $F$ that connects vertices from different components in $G$ is problematic because it creates a connection that doesn't exist in $G$. These edges are "invalid" and must be removed. Counting these invalid edges gives us the first part of the solution: the number of edges we need to remove from $F$.

After removing these invalid edges, $F$ might end up with more connected components than $G$. To fix this, we need to add edges to $F$ to merge these extra components until the number of connected components in $F$ matches that in $G$. Each additional component in $F$ requires one edge addition to merge it with another component.

Finally, we calculate the minimum number of operations by adding these two values:

• The number of invalid edges that need to be removed
• The number of extra connected components in $F$ that need to be merged

Implementation

Time Complexity: $\mathcal{O}(N + M \log(M))$

Copy
#include <functional>
#include <iostream>
#include <map>
#include <vector>

using std::cout;
using std::function;
using std::pair;
using std::vector;

DSU Implementation

Time Complexity: $\mathcal{O}(N + M)$

Copy
#include <array>
#include <iostream>
#include <numeric>
#include <vector>

using std::array;
using std::cout;
using std::vector;

/**