思路与算法

先检查愿望图是否对称且构成一个全体单环；两种环向分别统计各旋转能保留原位置的人数，代价为n减最多固定人数。

正确性说明

满足全部愿望的排列只可能是这个单环的两个方向及旋转。给定方向，学生原编号与环位置之差唯一决定使其固定的旋转，因此频次最大即保留人数最多。任一非固定学生至少移动一次；任意目标置换按非平凡循环分解执行命令恰移动每个非固定学生一次，故总代价恰是非固定人数。

复杂度

O(n)时间、O(n)空间，含愿望图、访问与两组旋转频次初始化。

易错点

互相希望相邻必须双向一致；多个分离的环不能组成一个座位大圆，必须-1。不能只考虑一个方向。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<array<int, 2>> a(n);
    for (auto &v : a) {
        cin >> v[0] >> v[1];
        --v[0];
        --v[1];
    }
    for (int i = 0; i < n; i++)
        for (int v : a[i])
            if (v < 0 || v >= n || v == i || (a[v][0] != i && a[v][1] != i)) {
                cout << -1 << "\n";
                return 0;
            }
    vector<int> p, seen(n);
    int u = 0, prev = -1;
    while (!seen[u]) {
        seen[u] = 1;
        p.push_back(u);
        int v = a[u][0] == prev ? a[u][1] : a[u][0];
        prev = u;
        u = v;
    }
    if (u != 0 || (int)p.size() != n) {
        cout << -1 << "\n";
        return 0;
    }
    int best = 0;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++) {
        best = max(best, ++x[(p[i] - i + n) % n]);
        best = max(best, ++y[(p[i] + i) % n]);
    }
    cout << n - best << "\n";
}