题意
给定一张由 \(N\) 个点和 \(M\) 条边组成的简单无向图 \(G\)，定义一个无向图是好的当且仅当这张图满足以下条件：
- \(1\) 号节点和 \(N\) 号节点不联通
- 图中不存在重边和自环
现有两人轮流采取操作，每轮操作如下：
- 选择两个点 \(u, v\)，将边 \((u, v)\) 加入图 \(G\) 中
当一方无法使得操作后的图 \(G\) 为好的时候，游戏结束，此时另一方获胜。
现给定 \(N, M\)，求在双方均采取最优策略的情况下的胜方。
- \(1 \le T \le 10^5\)
- \(2 \le N \le 10^5\)
- \(0 \le M \le \min\left\{\frac{N\left(N - 1\right)}{2}, 10^5\right\}\)
- \(\sum N, \sum M \le 2 \times 10^5\)
- \(G\) 满足题目中好的图的条件
题解
设最终局面下 \(1\) 号节点所在的联通块大小为 \(n\)，那么可以得出双方可以操作的步数为
\[\dfrac{N\left(N - 1\right)}{2} - M - n \left(N - n\right) \]可以发现其奇偶性决定了胜负，因此只需要考虑其奇偶性即可，由于式子的前半部分是给定的，因此双方的策略就是通过调整 \(n\) 的奇偶性来决定胜负。
可以发现当 \(N\) 为奇数时，\(n\) 和 \(N - n\) 中一定有一个数为偶数，因此上式的奇偶性是确定的，可以直接计算。
接下来讨论 \(N\) 为偶数的情况。
设 \(A\) 表示初始局面下 \(1\) 号节点所在的联通块大小，\(B\) 表示初始局面下 \(N\) 号节点所在的联通块大小。有如下结论：
- 若 \(A, B\) 奇偶性不同，那么先手必胜
- 反之考虑 \(\dfrac{N\left(N - 1\right)}{2} - M - A \times B\) 的奇偶性，若为奇数，那么先手必胜，反之后手必胜
证明如下：
设 \(S = \dfrac{N\left(N - 1\right)}{2} - M - A \times B\)。
不妨称在 \(S\) 的奇偶性下处于优势的一方为优势方，反之则称为劣势方。例如当 \(S\) 为奇数时，先手为优势方。
-
若 \(A, B\) 奇偶性相同，那么此时图中一定存在偶数个奇联通块，因此当劣势方尝试通过操作奇联通块改变 \(S\) 的奇偶性时，优势方一定可以通过操作另外的一个奇联通块使得 \(S\) 的奇偶性保持不变，因此优势方一定可以保持优势，最终获胜。
-
若 \(A, B\) 奇偶性不同，那么此时图中一定存在奇数个奇联通块，可以发现先手在第一次操作时可以选择一个奇联通块，并且使得 \(S\) 的奇偶性变得有利于自己。接下来图中一定存在偶数个奇联通块，当后手尝试通过操作奇联通块改变 \(S\) 的奇偶性时，先手一定可以通过操作另外的一个奇联通块使得 \(S\) 的奇偶性保持不变，因此先手一定可以保持优势，最终获胜。
时间复杂度 \(\mathcal{O}(N + M \alpha\left(N\right))\)，空间复杂度 \(\mathcal{O}(N)\)，可以通过。
Code
#include <bits/stdc++.h>
typedef long long valueType;
typedef std::vector<valueType> ValueVector;
template<bool sizeBalanced = true>
class DSU {
private:
valueType N;
ValueVector father, size;
public:
explicit DSU(valueType n = 0) : N(n), father(N, 0), size(N, 0) {
std::iota(father.begin(), father.end(), 0);
std::fill(size.begin(), size.end(), 1);
}
void resize(valueType n) {
N = n;
father.resize(N, 0);
size.resize(N);
std::iota(father.begin(), father.end(), 0);
std::fill(size.begin(), size.end(), 1);
}
valueType find(valueType x) {
return father[x] == x ? x : father[x] = find(father[x]);
}
bool unite(int x, int y) { // y -> x if !sizeBalanced
x = find(x), y = find(y);
if (x == y)
return false;
if (sizeBalanced && size[x] < size[y])
std::swap(x, y);
father[y] = x;
size[x] += size[y];
return true;
}
bool check(valueType x, valueType y) {
return find(x) == find(y);
}
valueType sizeOf(valueType n) {
return size[find(n)];
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
valueType T;
std::cin >> T;
for (int testcase = 0; testcase < T; ++testcase) {
valueType N, M;
std::cin >> N >> M;
DSU<true> dsu(N + 1);
for (int i = 0; i < M; ++i) {
valueType x, y;
std::cin >> x >> y;
dsu.unite(x, y);
}
valueType const A = dsu.sizeOf(1), B = dsu.sizeOf(N);
if (N & 1) {
valueType const X = N * (N - 1) / 2 - M;
if (X & 1)
std::cout << "First" << std::endl;
else
std::cout << "Second" << std::endl;
} else {
if ((A & 1) != (B & 1)) {
std::cout << "First" << std::endl;
} else {
valueType const X = N * (N - 1) / 2 - M - A * B;
if (X & 1)
std::cout << "First" << std::endl;
else
std::cout << "Second" << std::endl;
}
}
}
return 0;
}