ARC105E Keep Graph Disconnected 题解

ARC105E

正向考虑是很难的，从结果入手，发现最后一定是分别包含 \(1\)，\(n\) 的两个完全图。

考虑表示出这两个人一共加了多少边：\(\frac{n(n-1)}{2}-m-x(n-x)\)，\(x\) 表示点 \(1\) 所在集合的大小。

由于是判断先手还是后手必胜，所以只需看结果对 \(2\) 的余数，于是对 \(n\) 的奇偶进行分讨。

当 \(n\) 为奇数时，此时 \(x(n-x)\) 一定是偶数，这时只需要对 \(\frac{n(n-1)}{2}-m\) 进行讨论。

当 \(n\) 为偶数时：对 \(1\)，\(n\) 初始时所在的连通块大小进行讨论，分别记为 \(a\)，\(b\)。当 \(a\)，\(b\) 奇偶性相同时，由于其它所有连通块之和为偶数，所以连通块大小为奇数和偶数的连通块个数一定都为偶数，这时先后手不管怎样都无法改变局势，因为可以通过模仿对方的行动进行抵消。

当 \(a\)，\(b\) 奇偶性不同时，因为 \(a\)，\(b\) 先后手并不一定是 \(a\) 先手 \(b\) 后手，故先手一定可以改变最后的连通块的奇偶性，后手的操作都可以被先手抵消，故此时先手必胜。

时空线性。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector < int >
#define eb emplace_back
#define pii pair < int, int >
#define fi first
#define se second
#define TIME 1e3 * clock() / CLOCKS_PER_SEC
int Mbe;
mt19937_64 rng(35);
constexpr int N = 1e5 + 10;
int n, m;
int fa[N], sz[N];
int find(int x) {
	if(fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}
ll calc(int x) {
	return x * 1ll * (x - 1) / 2;
}
void solve() {
	cin >> n >> m;
	for(int i = 1; i <= n; ++i) {
		fa[i] = i;
		sz[i] = 0;
	}
	for(int i = 1; i <= m; ++i) {
		int u, v;
		cin >> u >> v;
		fa[find(u)] = find(v);
	}
	for(int i = 1; i <= n; ++i) ++sz[find(i)];
	ll x = find(1), y = find(n);
	if(x == y) {
		cout << "Second" << "\n";
		return;
	}
	if(n & 1) {
		if(calc(n) % 2 - m % 2) cout << "First" << "\n";
		else cout << "Second" << "\n";
		return;
	}
	if(sz[x] % 2 != sz[y] % 2) {
		cout << "First" << "\n";
		return;
	}
	if((calc(n) - m - sz[x] % 2) & 1) cout << "First" << "\n";
	else cout << "Second" << "\n";
} 
int Med;
int main() {
	fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
	ios :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int T;
	cin >> T;
	while(T--) solve();
	cerr << TIME << "ms\n";
	return 0;
}