Problem - 1411C - Codeforces

题意:

你会得到一个n×n的棋盘。棋盘的行和列从1到n编号。单元格(x,y)位于列号x和行号y的交点上。

车是一个棋子，它可以在一个回合内垂直或水平地移动任何数量的单元。棋盘上有m个车(m

在一个回合中，你可以在垂直或水平方向上移动其中一个车的任何数量的单元。此外，它在移动后不应该受到任何其他车的攻击。将所有的车放在主对角线上所需的最少步数是多少？

棋盘的主对角线是所有的单元格（i,i），其中1≤i≤n。

输入
第一行包含测试案例的数量t（1≤t≤103）。下面是对t个测试用例的描述。

每个测试案例的第一行包含两个整数n和m--棋盘的大小和车的数量（2≤n≤105，1≤m

所有测试案例的n之和不超过105。

输出
对于每一个测试实例，打印一个整数--将所有棋子放在主对角线上所需的最小棋步数。

可以证明，这总是可能的。

题解:
因为我们要把点都移到对角线上,并且没有一对车共用一行或一列的情况。

我们不妨倒着来看,如果对角线上的点设为(i,i),如果对于这样的点只有一个点在他攻击范围内,是不是可以直接移动到这个点,当然也会有几个点在一个对角线点的攻击范围内的,对于这样的点,是不是只用走两步即可

那么如何判断是否冲突了呢?
可以用并查集维护，对于点(x,y)，用并查集合并x和y，表示(x,x)和(y,y)在一个点(x,y)的攻击范围内，
如果合并之前发现x和y已经在同一集合，那么说明和其他点出现了冲突，此时总步数需要+1。

最后要注意的是，如果一个点一开始就在对角线上，那么忽略不计。
 

#include
#include
#include