显然终止态是只剩两个连通块,一个包含 \(1\) 另一个包含 \(n\),并且两个连通块内的边数均为 \(\frac{sz(sz-1)}{2}\)。
如果只在连通块内连边,那么能连的边的总数是 \(\frac{n(n-1)}{2} - \sum\limits_{i=1}^{cnt} \frac{sz_i (sz_i - 1)}{2}\),其中 \(cnt\) 为连通块总数,\(sz_i\) 为第 \(i\) 个连通块的点数。下文钦定 \(1\) 所在连通块为第 \(1\) 个连通块,\(n\) 所在连通块为第 \(2\) 个连通块。
然而还可以在连通块之间连边,这样还需要 \(cnt - 2\) 次连边使得原图仅剩第 \(1\) 个和第 \(2\) 个连通块。
在连通块之间连边时,设两个连通块的 \(sz\) 分别为 \(x,y\),那么会新增 \(xy-1\) 条块内部的连边。如果 \(x,y\) 均为奇数,那么不会影响能连的边数的奇偶性;如果 \(x,y\) 有一个为偶数,那么能连的边数的奇偶性会改变。
据此考虑按 \(n\) 的奇偶性分类讨论。
- \(n \bmod 2 = 1\):最终 \(sz_1\) 和 \(sz_2\) 必然一奇一偶。此时合并偶数块的次数可以算出来。
- \(n \bmod 2 = 0\):最终 \(sz_1\) 和 \(sz_2\) 两奇或两偶。如果初始 \(sz_1\) 和 \(sz_2\) 奇偶性不相同,那么先手可以控制最终 \(sz_1\) 和 \(sz_2\) 的奇偶性,此时先手必胜:否则把其他连通块和第 \(1,2\) 个连通块合并的贡献抵消,可以忽略。此时偶数块的合并次数也可以算出来了。
code
// Problem: E - Keep Graph Disconnected
// Contest: AtCoder - AtCoder Regular Contest 105
// URL: https://atcoder.jp/contests/arc105/tasks/arc105_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 100100;
int n, m, fa[maxn], a[maxn], sz[maxn];
pii E[maxn];
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
inline void merge(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
fa[x] = y;
sz[y] += sz[x];
}
}
void solve() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
fa[i] = i;
a[i] = 0;
sz[i] = 1;
}
for (int i = 1, u, v; i <= m; ++i) {
scanf("%d%d", &u, &v);
merge(u, v);
E[i] = make_pair(u, v);
}
for (int i = 1; i <= m; ++i) {
++a[find(E[i].fst)];
}
ll k = 0, cnt = 0, c0 = 0, c1 = 0;
for (int i = 1; i <= n; ++i) {
if (fa[i] == i) {
++cnt;
c0 += (sz[i] % 2 == 0);
c1 += (sz[i] & 1);
k += 1LL * sz[i] * (sz[i] - 1) / 2 - a[i];
}
}
if (n & 1) {
k += cnt - 2;
k ^= ((c1 - 1) / 2);
k ^= (c0 ^ 1);
puts((k & 1) ? "First" : "Second");
} else {
if ((sz[find(1)] ^ sz[find(n)]) & 1) {
puts("First");
return;
}
if ((sz[find(1)] & 1) && (sz[find(n)] & 1)) {
c1 -= 2;
} else {
c0 -= 2;
}
k += cnt - 2;
k ^= (c1 / 2);
k ^= c0;
puts((k & 1) ? "First" : "Second");
}
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
/*
分类讨论,如果两个连通块点数是 x,y
此时当前操作的人在它们之间连了一条边,会新增 xy-1 条边
如果 x,y 都是奇数,无影响
如果 x,y 有一个为偶数,剩余边数奇偶性改变
如果 n 是奇数,最后两个连通块肯定是一奇一偶
如果 n 是偶数,最后要么两奇要么两偶
*/
- Disconnected AtCoder Regular Contest Graphdisconnected atcoder regular contest atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest sliding atcoder regular contest degree atcoder regular contest 167 atcoder regular contest 164 atcoder regular contest builder subsegments atcoder regular contest