[ARC105E] Keep Graph Disconnected题解

题目

考虑加任意一条边时都会输的图的状态：图被分成两个强联通分量，每一个强联通分量都是一个完全图。

也就是说，假设一开始节点 $1$ 和节点 $n$ 不联通，那么还可以加 $\frac{n(n-1)}2-m-cnt_1(n-cnt_1)$ 次，其中 $cnt_x$ 代表 $x$ 所在联通块大小。

若 $n$ 为奇数
- 此时 $cnt_1(n-cnt_1)$ 一定是偶数，只用对 $\frac{n(n-1)}2-m$ 进行讨论，~~你偏要加上 $cnt_1(n-cnt_1)$ 也不是不行~~。
否则：
- 若 $cnt_1=cnt_n$ ：
  - 此时先手一定可以选择 $cnt_1$ 和 $cnt_n$ 的奇偶性（通过增加联通块的点），所以先手必胜。
  - 否则，对 $\frac{n(n-1)}2-m-cnt_1(n-cnt_1)$ 进行判断。

Code：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int t, n, m;
int f[200100], cnt[200100];
int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> t;while (t--) {cin >> n >> m;for (int i = 1; i <= n; i++) {f[i] = i;cnt[i] = 0;}for (int i = 1; i <= m; i++) {int a, b;cin >> a >> b;f[find(b)] = find(a);}for (int i = 1; i <= n; i++) {cnt[find(i)]++;}if (find(1) == find(n)) {cout << "Second\n";}else if (n % 2) {if (((n * (n - 1) / 2) - m) % 2) cout << "First\n";else cout << "Second\n";}else {if (cnt[find(1)] % 2 != cnt[find(n)] % 2) {cout << "First\n";}else {if (((n * (n - 1) / 2) - m - cnt[find(1)] * (n - cnt[find(1)])) % 2) cout << "First\n";else cout << "Second\n";}}}return 0;
}