Problem

Luogu P2881
Given \(n\) numbers and \(m\) relations of the form \(a > b\), determine how many additional pairwise comparisons are needed to deduce the total order of all numbers.

Solution

Two approaches exist: Floyd‑Warshall and topological sort. This article focuses on the latter.

If no relations are given, we need to check every pair, which requires

The problem reduces to counting all pair that are already comparable (directly or transitively). We build a directed graph where an edge \(u \to v\) means \(u > v\). Then two numbers are comparable iff there is a path from one to the other.

Floyd‑Warshall Approach

Floyd‑Warshall typically computes all‑pairs shortest paths. Here we repurpose it to compute transitive closure: let \(\mathit{reachable}[u][v]\) be 1 if \(u\) can reach \(v\). The triangle inequality becomes:

for (int k = 0; k < n; ++k)
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            reachable[i][j] |= reachable[i][k] & reachable[k][j];

After running this, if \(\mathit{reachable}[i][j]\) or \(\mathit{reachable}[j][i]\) is true, the answer is decremented by 1. However, \(n\le 1000\) makes the \(O(n^3)\) algorithm too slow.

Topological Sort Approach

Because the graph is acyclic (a cycle would imply contradictions like \(a>b, b>c, c>a\)), we can process vertices in topological order. For each vertex \(x\), we propagate its reachable set to all its outgoing neighbours. Initially, each vertex can reach itself. When we process an edge \(x \to i\), we set \(\mathit{reachable}[i] \mid= \mathit{reachable}[x]\).

while (!q.empty()) {
    int x = q.front(); q.pop();
    for (int i = 0; i < n; ++i) {
        if (adj[x][i]) {
            reachable[i] |= reachable[x];
            if (--indeg[i] == 0) q.push(i);
        }
    }
}

With adjacency lists, the complexity is \(O(n(n+m))\), which passes the constraints.

Bitset Optimisation

Bitsets allow bitwise operations on a compact representation, reducing constant factors significantly. A bitset of size \(n\) can replace a bool array and supports operations like |=, &=, etc.

Optimised Floyd‑Warshall

Instead of triple loops we iterate over the intermediate vertex \(k\) and for each target \(j\) where an edge \(k \to j\) exists, we or the reachable set of \(k\) into that of \(j\):

for (int k = 0; k < n; ++k)
    for (int j = 0; j < n; ++j)
        if (adj[k][j])
            reachable[j] |= reachable[k];

Optimised Topological Sort

Similarly, the topological propagation becomes:

while (!q.empty()) {
    int x = q.front(); q.pop();
    for (int i = 0; i < n; ++i) {
        if (adj[x][i]) {
            reachable[i] |= reachable[x];
            if (--indeg[i] == 0) q.push(i);
        }
    }
}

After either method, the number of missing comparisons is

Alternatively, one can simply count for each unordered pair (i,j) whether reachable[i][j] or reachable[j][i] is true, and subtract that count from \(n(n-1)/2\).)