We'll model Dance Royale as a directed graph with ~N~ nodes (one per location) and up to ~N~ edges (one per transition from a node to its destination node, if any).

Each component of the graph may be processed independently of the other components, and contains either exactly one cycle or no cycles. If the component contains a cycle, then the remainder of the component consists of trees rooted at nodes on that cycle (such that, if there's an edge from node ~i~ to node ~j~, then node ~j~ is node ~i~'s parent). Otherwise, if the component is acyclic, then the entire component is a single tree rooted at a node with out-degree ~0~.

We'll iterate over all ~N~ nodes in any order, and each time we come across one whose component has not yet been processed, we'll process it by repeatedly following its edges forward until either arriving back at a previously-visited node (thus indicating a cycle with some length ~C~, which we can find easily), or arriving at a node with out-degree ~0~ (thus indicating an acyclic component).

In either case, we'll perform either a DFS or BFS throughout the component on the transpose graph (with all edges reversed), starting from the node arrived at in the above process (that is, any node on the cycle if there is one, or otherwise the ~0~-degree node). Let ~F(x)~ be the total number of players at nodes which are at a distance of ~x~ away from the starting node (these totals can be stored in a hash map to allow them to be efficiently reset to ~0~ between different components).

Now, if the component has a length-~C~ cycle, then all players at distances ~x~, ~x+C~, ~x+2C~, and so on will end up at the same position along the cycle after an infinite amount of time (for ~0 \le x < C~). Letting ~G(x)~ be this sum, this will result in ~\frac{G(x) \times (G(x)-1)}{2}~ dance battles occurring (for each possible ~x~). Otherwise, if the component is acyclic, then the situation is similar but without any periodicity by ~C~ — instead, there will simply be ~\frac{F(x) \times (F(x)-1)}{2}~ dance battles (for each possible ~x~).

The time complexity of this algorithm is ~\mathcal O(N+M)~.