Official

E - Cables and Servers Editorial by en_translator


Consider the graph where the servers are the vertices and the cables are the edges.

For each connected component, find the vertices that belongs to it, and the “excessive” edges. This can be done with DFS (Depth-First Search) or BFS (Breadth-First Search), or a data structure like DSU (Disjoint Set Union).
Modifying one end of an “excessive” edge always reduces the number of connected components. Conversely, no matter how the edges are modified, the number of connected component changes by at most one. Thus, repeating this modification minimizes the number of operations required.

You can easily implement it by considering connected components with more “excessive” edges first.

Writer’s solution (C++)

posted:
last update: