和谐并处的车

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

给定一个 $n\times n$ 的象棋棋盘。棋盘的行和列编号从 $1$ 到 $n$ 。单元格 $(x,y)$ 位于第 $x$ 列和第 $y$ 行的交点。

“车” 是一种国际象棋棋子，每一步可以沿着垂直或水平方向移动任意格数。棋盘上有 $m$ 个车（ $m<n$ ），它们被放置在棋盘上，且任意两个车不会互相攻击。也就是说，没有任意一对车处于同一行或同一列。

每一步，你可以选择一个车，将其沿垂直或水平方向移动任意格数。移动后，该车不能被其他任何车攻击。请问，最少需要多少步才能将所有车都放到主对角线上？

棋盘的主对角线是所有 $(i,i)$ 的单元格，其中 $1\leqq i\leqq n$ 。

输入描述：

第一行包含测试用例数 $T（1\leqq T\leqq 10^3）$ 。接下来是 $T$ 个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ，分别表示棋盘的大小和车的数量 $（2\leqq n\leqq 10^5，1\leqq m<n）$ 。接下来的 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ，表示第 $i$ 个车的位置，即该车位于 $(x_i,y_i)（1\leqq x_i,y_i\leqq n）$ 。保证初始状态下没有两辆车互相攻击。

所有测试用例中 $n$ 的总和不超过 $10^5$ 。

输出描述：

对于每个测试用例，输出一个整数，表示将所有车放到主对角线上所需的最小步数。

可以证明一定存在可行方案。

示例1

输入：

4
3 1
2 3
3 2
2 1
1 2
5 3
2 3
3 1
1 2
5 4
4 5
5 1
2 2
3 3

输出：

1
3
4
2

说明：

前三个测试用例的可能移动方案：

1. $(2,3)\to (2,2)$
2. $(2,1)\to (2,3)，(1,2)\to (1,1)，(2,3)\to (2,2)$
3. $(2,3)\to (2,4)，(2,4)\to (4,4)，(3,1)\to (3,3)，(1,2)\to (1,1)$

解题思路

本题核心是置换环结合并查集的图论模型求解最小移动步数。初始车辆互不攻击，意味着所有列坐标、行坐标各自唯一，可将每组坐标 $(x,y)$ 抽象为映射关系，构成置换结构。使用并查集维护行列节点的连通性，统计两个关键值：ok 是本身已在主对角线（$x=y$）的车辆数，c 是合并时形成新置换环的次数。通过推导可得最小步数公式：$m-ok+c$。并查集搭配路径压缩，单次查询与合并均摊复杂度接近 $O(1)$，可以高效应对 $n\le 10^5$、多组测试用例的数据约束。

总结

核心逻辑：把车辆位置转化为置换环模型，借助并查集统计自环数量与非自环置换环个数，代入公式直接计算答案。
关键操作：初始化并查集、合并每组坐标对应的行列节点、统计自环数与环数量、套用公式输出结果。
效率保障：路径压缩优化后的并查集运算极快，线性复杂度完美适配题目大数据范围。

代码简要说明

1. 并查集基础：fd 函数实现带路径压缩的查找，u 函数完成节点合并，同时统计自环数 ok 和置换环数 c。
2. 多组用例处理：每组测试用例先重置并查集、清零统计变量，再依次读取每辆车的坐标并执行合并。
3. 公式计算：根据结论 $m-ok+c$ 算出最小步数并输出，逻辑简洁且运行高效。

代码内容

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=100010;
const ll INF=1e18;
const ll M=1e6+10;
const ll mod=1e9+7;

ll p[N];
ll fd(ll u){
    if(p[u]==u) return u;
    return p[u]=fd(p[u]);
}
ll c,ok;
void u(ll a,ll b){
    if(a==b){ok++;return;}
    ll ra=fd(a),rb=fd(b);
    if(ra==rb) c++;
    else p[rb]=ra;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    ll t; cin>>t;
    while(t--){
        ll n,m; cin>>n>>m;
        c=0; ok=0;
        for(ll i=1;i<=n;i++) p[i]=i;
        for(ll i=1;i<=m;i++){
            ll x,y; cin>>x>>y;
            u(x,y);
        }
        cout<<m-ok+c<<endl;
    }
    return 0;
}