在一个 \(n \times n\) 的棋盘上有 \(m(m < n)\) 个棋子。若棋子处于同一行或同一列便认为他们可以互相攻击。初始时棋子之间均不可互相攻击。你可以进行若干次操作，每次操作可以将棋子纵向移动任意格或横向移动任意格，要求移动之后棋子之间不能互相攻击。求使得棋子均处在主对角线上的最小操作次数。
这道题本该很简单，但当时想的时候一如既往的失了智，导致做得很慢。
我们先考虑纵向移动的情况，一颗棋子 \((x, y)\) 要移动到 \((y, y)\)。理想的情况是棋子移动过去，没有冲突，但是如果第 \(y\) 行已被占用，比如说被 \((y, z)\) 占用，就需要 \((y, z)\) 挪位置。挪到哪里呢，挪到 \((z, z)\) 显然是可靠的。但是如果第 \(z\) 行也被占用了呢？那就继续往前挪。这样一来要么成一条链，要么成一个环。若是成一个环的话，那就需要一枚棋子移动到空旷的地方暂且避让，这就会使操作数增加一步。于是每次连边 \((x, y) : x \rightarrow y\) ，然后数环即可。
那么横向移动的情况呢，可以发现是建反向边，和纵向移动一样，两种移动方式我们采取一种即可。
当时的思路是很混乱的，只想到第一层，就是一个环或者一条链的情况，然后各种判断，果然还是一叶障目了。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int edg[100005];
bool vis[100005];
int dfs(int u) {
if (u == 0) return 0;
if (vis[u]) return u;
vis[u] = true;
return dfs(edg[u]);
}
int main() {
int T = 0;
scanf("%d", &T);
for (int G = 1; G <= T; G++) {
int n = 0, m = 0, ans = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
edg[i] = 0, vis[i] = false;
for (int i = 1; i <= m; i++) {
int x = 0, y = 0;
scanf("%d%d", &x, &y);
if (x != y) ans++;
edg[x] = y;
}
for (int i = 1; i <= n; i++) {
if (edg[i] == 0 || edg[i] == i)
continue;
if (!vis[i]) {
if (dfs(i) == i) ans++;
}
}
printf("%d\n", ans);
}
return 0;
}