Consider tracking the state of the graph \(G\), namely, the vertices adjacent to each vertex, and the vertices the pieces are placed.

When creating a vertex or performing a contraction, if you arbitrarily choose one vertex from the endpoints of the edge to be contracted and treat it as a new vertex, it costs \(O(N+M)\) time at worst, for a total of \(O(Q(N+M))\) time, so this will not finish within the execution time limit. Can we come up with a clever choice of vertex when performing a contraction for a speedup?

First, let us consider the time complexity required to update the information. Let \(u\) and \(v\) be the endpoints of the edge to be contracted, \(P_u\) and \(P_v\) be the number of pieces on vertex \(u\) and \(v\), respectively, and \(Q_u\) and \(Q_v\) be the number of edges incident to \(u\) and \(v\), respectively. If \(u\) is treated as a new vertex, the following process is performed:

• Move all pieces on \(v\) to \(u\).
• For each vertex \(x\) adjacent to \(v\), except for \(u\), if \(x\) is not adjacent to \(u\), newly connect \(x\) and \(u\) with an edge.
• Remove the edges connecting \(v\) and other edges.
• Remove \(v\).

The first step can be done in \(O(P_v)\) time.
The second step naively costs \(O(Q_uQ_v)\) time, but it can be reduced to \(O(Q_v\log Q_u)\), which is \(O(Q_v\log N)\), by managing the adjacency list of each vertex in an appropriate data structure (like std::set). The third step costs \(O(Q_v\log N)\) time if you are managing the adjacency list in a std::set-like data structure. The fourth step can be done in constant time. Therefore, the procedure can be completed in at most \(O(P_v+Q_v\log N)\) time, which is in \(O((P_v+Q_v)\log N)\).

Here, we claim that the total time complexity required for all contractions can be bounded by \(O((N+M)\log (N+M)\log N)\), if you treat \(u\) as the new vertex after the contraction if and only if \((P_u+Q_u)>(P_v+Q_v)\). Note that the procedure is performed at most \((N-1)\) time, since every contraction reduces the number of vertices by one.

TBC