Educational Codeforces Round 188 (Rated for Div. 2)——CF-2204-D. Alternating Path（无向图下，二分图与没有奇数环是等价的） · znzryb
## 题目大意
**题目总结**
给定一个无向图（无重边、无自环），你要给每条边指定一个方向，得到有向图。
定义一条点序列 $v_1,v_2,\dots,v_k$（长度可任意大，点可重复）是“交替路径”，当且仅当相邻边方向按如下模式交替：
- 第 1 条边是 $v_1 \to v_2$；
- 第 2 条边是 $v_3 \to v_2$；
- 第 3 条边是 $v_3 \to v_4$；
- 第 4 条边是 $v_5 \to v_4$；
- 之后继续这样“顺、逆、顺、逆”交替。
一个点 $v$ 被称为“beautiful”，如果在原图中所有从 $v$ 出发的路径（不要求简单路径，允许重复点和边）在你定向后都满足上面的交替性质。
目标：对每个测试用例，求最多能让多少个点成为 beautiful。
---
**输入输出要求（题意层面）**
- 输入有多组测试。
- 每组给 $n,m$ 和 $m$ 条无向边。
- 需要输出一个整数：该组图中可成为 beautiful 的点数最大值。
---
**样例**
```
Input
4
8 9
1 3
1 4
2 3
2 4
5 6
6 7
7 8
8 5
6 8
4 0
6 2
1 5
2 3
1 0
```
```
Output
2
4
4
1
```
---
**样例解释**
- 第 1 组输出 `2`：最多只能让 2 个点满足“从该点出发的任意路径都交替”。
- 第 2 组输出 `4`：图中没有边，任意从点出发的路径都平凡成立，所以 4 个点都可 beautiful。
- 第 3 组输出 `4`：最多可让 4 个点满足条件。
- 第 4 组输出 `1`：只有 1 个点且无边，因此这个点可 beautiful。
## 思路讲解
不难发现，有奇数环的环，搞出来一个这个矛盾的方案是非常容易的。
当然，这个是反向论证，我们再正向论证一下，为什么我们一定要求这张图是一个二分图。不难发现，一张图上，一个点要么其所有的边都是出去的，要么所有边都是进去的。
你说你如果违反这一要求会怎么样？那么就会一定不符合这个题设要求（这个应该是非常显然的，因为这样子会导致一个 a→b→c 序列，但是题设要求是 a→b<-c）。
## AC代码
::: 源代码
```cpp
/**
* Problem: D. Alternating Path
* Contest: Educational Codeforces Round 188 (Rated for Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2204/problem/D
* Created: 2026-03-16 23:42:43
* 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;
/*
*
*/
struct U_step{
ll u,step/*,fa*/;
};
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);
}
vector<char> vis(N+2);
vector<char> color(N+2);
ll ans=0;
for (int i=1;i<=N;++i) {
if (vis[i]) {
continue;
}
queue<U_step> q;
q.push({i,1});
vis[i]=true;
color[i]=1;
vector<ll> cnt(2);
cnt[color[i]]++;
bool is_erfen=true;
while (!q.empty()) {
auto [u,step]=q.front();
q.pop();
for (auto v:g[u]) {
// if (v==fa) continue;
if (vis[v]) {
if (color[v]!=(step+1)%2) {
is_erfen=false;
}
continue;
}
vis[v]=1;
color[v]=(step+1)%2;
cnt[color[v]]++;
q.push({v,step+1});
}
}
if (!is_erfen) continue;
ans+=max(cnt[0],cnt[1]);
// ans+=(lans+1)/2;
}
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/contest/2204/submission/367015011
1
6 2
1 5
2 3
1
8 9
1 3
1 4
2 3
2 4
5 6
6 7
7 8
8 5
6 8
*/
```
:::
## 心路历程（WA，TLE，MLE……）