Particle Swapping, solution

Time complexity: O(nm + n^2 log n)

We will answer all possible {n choose 2} queries. Let G be the input graph. We create an auxiliary graph H with vertex set V(G)\times V(G), denoting the possible positions of particles in the system. We put an edge in H between every two states that are within a single move. Note that there are at most 2*2*|V(G)|*|E(G)| possible moves, so |V(H)|=O(n^2) and |E(H)|=O(nm). For a vertex (A,B) of H, we define its safeness as the Euclidean distance between nodes A and B on the plate. The task boils down to finding, for every (A,B)\in V(H), the max-min value of the safeness on a path in H from (A,B) to (B,A).

Let us sort the vertices of H with respect to their safeness. We will reconstruct H from scratches, adding the vertices in the order of decreasing safenesses. During this process we maintain the partition of already added vertices of H into connected components. Each connected component is represented as a representative vertex and a vector of its members; moreover, each vertex remembers the component it belongs to. Note that the max-min safeness for a pair (A,B) corresponds to the safeness of the currently added vertex of H at the first moment when (A,B) and (B,A) fall into the same connected component.

When we add the next vertex u, we create a new connected component and iterate through all the edges adjacent to u. For each edge connecting it to an already added vertex, we add this edge to the graph and update the partition into connected components. If addition of this edge did not merge any two connected components (this can be verified in constant time, since a vertex remembers its component), we do nothing. Otherwise, we need to make the merge. For this, we do the standard trick: we merge the smaller component into the larger. Let's assume we merge component C1 into C2. We iterate through the whole list of members of C1, update the pointers to the component we belong to, and add all the elements of C1 to the vector of elements of C2. Moreover, for every vertex (A,B) of C1 for which we do not know the answer so far, we check whether (B,A) is in C2 (this is a constant-time check, since for each vertex we remember the component it belongs to). If this is the case, we put as the answer for (A,B) the safeness of the currently added vertex of V(H).

Each merge is performed in time linear in the size of the smaller component, which means that each vertex contributes to the total time spent on merging at most log |V(H)| = 2 log n times. Observe that there are at most |V(H)|-1 = O(n^2) merges performed, whereas each edge of H for which a merge was not performed is processed in constant time. Time complexity O(nm + n^2 log n) follows.