2025 ICPC Asia Manila Regional（2025 ICPC 亚洲 菲律宾 马尼拉）——J. Tic-Tac-Toe on a Graph（遇到图上问题，没有特殊结构，那么基本就是分类讨论，按度数进行分类讨论） · znzryb
## 题目大意
**题目描述**
Alice 和 Bob 在一个无向简单图上玩改进版的井字棋游戏。这个图有 $n$ 个顶点（代表方格）和 $m$ 条边。
游戏规则如下：
1. 初始时，所有顶点都是空的。
1. 两人轮流行动，Alice 先手。
1. 在 Alice 的回合，她选择一个空的顶点并画上 `X`。
1. 在 Bob 的回合，他选择一个空的顶点并画上 `O`。
1. 游戏总共进行 5 个回合，也就是说 Alice 总是行动 3 次，Bob 总是行动 2 次。
1. 如果 Alice 能够将她画了 `X` 的 3 个顶点连成一条**长度为 3 的路径**（注意：这 3 个顶点在路径中的顺序不一定与她落子的顺序相同），那么 Alice 获胜。如果 Bob 能阻止这一切发生，则 Bob 获胜。
假设双方在第一步之后都采取**完美策略**。请计算：Alice 有多少种可能的**第一步**选择，使得无论 Bob 随后如何应对，她都必胜？
**输入格式**
第一行包含两个由空格分隔的整数 $n$ 和 $m$（$5 \le n \le 2 \times 10^5, 0 \le m \le \min(2 \times 10^5, n(n - 1)/2)$），分别表示图的顶点数和边数。
接下来 $m$ 行，每行包含两个由空格分隔的整数 $u$ 和 $v$（$1 \le u, v \le n$），表示顶点 $u$ 和 $v$ 之间有一条边。
保证图中没有自环和重边。
**输出格式**
输出一个整数，表示能让 Alice 必胜的初始落子位置的数量。
**样例输入**
```
8 9
1 2
1 4
1 5
2 3
2 7
3 4
3 5
3 6
4 6
```
**样例输出**
```
5
```
**样例解释**
对于该图，如果 Alice 第一步下在顶点 1、2、3、4 或 5，那么在双方完美发挥的情况下，她必定能获胜。
以第一步下在顶点 1 为例，其中一种可能的游戏进程是：
- Alice 在 1 画 `X`
- Bob 在 4 画 `O`
- Alice 在 2 画 `X`
- Bob 在 3 画 `O`
- Alice 在 7 画 `X`
此时 Alice 在 1、2、7 画了 `X`，它们构成了一条长度为 3 的路径（1-2-7），因此 Alice 获胜。
如果她第一步下在 6、7 或 8，那么在 Bob 完美应对的情况下，她注定会输。
必胜的起始点有 5 个，因此输出 5。
## 思路讲解
遇到图上问题，**没有特殊结构以及这个数据比较大，那么基本上就可以排除 dp 的可能性了**。
那说白了，我们还有其他工具吗？
我们回归原始，对度数进行分类讨论。
首先，度数 ≥ 4，一定是必胜起始点。
度数为 3 的时候，不难得出：⚠️ 注意：需要两个，否则你刚走一步，他就把你唯一一条生路给堵死了，你不就死了吗。
度数为 2 的情况：
度数为 1 自然是不可能的。
然后好像就做完了？绷不住了
## AC代码
AC
[https://codeforces.com/gym/106262/submission/365635347](https://codeforces.com/gym/106262/submission/365635347)
::: 源代码
```cpp
/**
* Problem: J. Tic-Tac-Toe on a Graph
* Contest: 2025 ICPC Asia Manila Regional
* Judge: Codeforces
* URL: https://codeforces.com/gym/106262/problem/J
* Created: 2026-03-06 11:12:30
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
void Solve() {
ll N,M;
cin >> N >> M;
vector<vector<ll>> g(N+2);
for (int i=1;i<=M;++i) {
ll u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
ll ans=0;
for (int u=1;u<=N;++u) {
if (SZ(g[u])>=4) {
ans++;
continue;
}
if (SZ(g[u])==3) {
set<ll> st(all(g[u]));
st.insert(u);
ll cnt=0;
for (auto to:g[u]) {
for (auto toto:g[to]) {
if (!st.contains(toto)) {
++cnt;
break;
}
}
}
if (cnt>=2) {
++ans;
}
}else if (SZ(g[u])==2) {
set<ll> st(all(g[u]));
st.insert(u);
ll cnt=0;
for (auto to:g[u]) {
ll not_in_st=0;
for (auto toto:g[to]) {
if (!st.contains(toto)) {
++not_in_st;
}
if (not_in_st>=2) {
++cnt;
break;
}
}
}
if (cnt>=2) {
++ans;
}
}
}
cout<<ans<<'\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
// cin >> lT;
// for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/gym/106262/submission/365635347
*/
```
:::
## 心路历程（WA，TLE，MLE……）