[ARC105E] Keep Graph Disconnected

NOIP 模拟赛原题，赛时还是没切。

正解奇偶性。

考虑最终不能走的时候是什么情况，当且仅当图中只剩下两个联通块了。设其中一个联通块的点数为 \(k\)，那么另一个的点数为 \(n - k\)。所以两人一共的操作次数为 \(sum = \frac{n \times (n-1)}{2}-m-k \times (n - k)\)。显然如果 \(sum\) 为偶数，后手赢；否则先手赢。因为前面 \(\frac{n \times (n-1)}{2}-m\) 已经确定了，所以只需要分析 \(k \times (n - k)\) 的奇偶性即可，故按 \(n\) 的奇偶进行分类讨论。

注：每一次有效的连边可以理解为选两个联通块进行合并，\(cnt_{i}\) 表示点 \(i\) 所在联通块大小。

• \(n\) 为奇数。\(k\) 和 \(n-k\) 中一定有一个为偶数，则 \(k \times (n-k)\) 为偶数，直接判断 \(\frac{n \times (n-1)}{2}-m\) 的奇偶性即可。

• \(n\) 为偶数。不能直接判断奇偶，还需要分类讨论。

1. 如果最初 \(1\) 所在的联通块和 \(n\) 所在的联通块的大小的奇偶性相同的话，那么其它奇数大小的联通块一定有偶数个，假设最开始（把 \(cnt_{1}\) 和 \(cnt_{n}\) 视为 \(k\) 和 \(n-k\)）的胜方为 \(A\)，那么当 \(B\) 想用一个奇数大小的联通块翻盘的时候，\(A\) 总是可以再用一个奇数大小的联通块再翻盘，所以最终的赢家为 \(A\)。

2. 如果最初 \(1\) 所在的联通块和 \(n\) 所在的联通块的大小的奇偶性不相同的话，那么奇数大小的联通块个数一定为奇数。先手可以直接使用一个奇数大小的联通块来使自己获胜，之后一直选和对方相同奇偶的联通块即可，所以先手必胜。

用并查集维护每个联通块大小。