题解：P15547 「Stoi2037」白色风车

· · 题解

本文所有图片均使用大佬 @EternalAlexander 的 OI Painter 制作。

题意简述

给定一个无向图，两个人 R 和 L 初始分别位于 x 和 y。每秒可以沿一条边移动，R 最多可以回头一次，L 不能回头。是否存在一种无限移动的策略，使得从时刻 t 开始，两人的位置始终处于某条边的两端。

其中，回头指连续两次经过同一条边。

解题思路

首先，题目给出的图不保证连通，所以先判断两个人是否在一个连通块内。如果不在，输出 No。

注意到永远需要无限次移动，那么连通块内必须有环。如果没有环，也就是一棵树，输出 No。

图中有环又分为了两种情况：奇环和偶环。

奇环

如果是奇环，那么两人走到环上后往奇数条边一侧走，必定会有手牵手，消耗一次回头次数在环上跑就行了，直接输出 Yes。

::::info[图片示例]

![] (https://cdn.luogu.com.cn/upload/image_hosting/p2h5mw6g.png)

::::

偶环（二分图）

一个图是二分图当且仅当它不包含奇环。

考虑对二分图染色成两部分。

如果点 x 与点 y 在同一部分，那么每次移动也都在同一部分。也就是说，R 和 L 永远会间隔一个点，没办法手牵手，输出 No。

::::info[图片示例]

::::

否则，和奇环一样，走到环上后往奇数条边一侧走，必定会有手牵手，消耗一次回头次数在环上跑就行了，输出 Yes。

::::info[图片示例]

::::

判断树和环都可以在一次 dfs 内进行。

dfs 进行二分图染色，如果颜色有冲突，则存在奇环；如果访问到非上个节点的点，则不是树。

深搜结束后如果这两者都没有，则是一颗树。

完整代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
int dfn[N], ltk[N], col[N], n, m, x, y, cnt, dep;
bool fl, vis[N], tr;
vector<int> g[N];
inline int read(){
    int res = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        res = res * 10 + c - '0';
        c = getchar();
    }
    return res * f;
}
void dfs1(int x){
    if (ltk[x]) return ;
    ltk[x] = cnt;
    for (int i = 0; i < g[x].size(); i++)
        dfs1(g[x][i]);
}
void dfs2(int x, int cl, int lst){
    col[x] = cl, vis[x] = 1;
    for (int i = 0; i < g[x].size(); i++){
        int y = g[x][i], nc = 1 - cl;
        if (vis[y]){
            if (nc != col[y]) fl = 1;
            if (y != lst) tr = 0;
            continue;
        }
        dfs2(y, nc, x);
    }
}
void init(){
    for (int i = 1; i <= n; i++){
        g[i].clear(), ltk[i] = 0, vis[i] = 0, col[i] = 0;
    }
    cnt = 0, fl = 0, tr = 1;
}
void solve(){
    init();
    n = read(), m = read(), x = read(), y = read();
    for (int i = 1; i <= m; i++){
        int u = read(), v = read();
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
        if (!ltk[i])
            cnt++, dfs1(i);
    if (ltk[x] != ltk[y]){
        puts("No");
        return ;
    }
    dfs2(x, 0, -1);
    if (tr){
        puts("No");
        return ;
    }
    if (fl){
        puts("Yes");
        return ;
    }
    if (col[x] == col[y]){
        puts("No");
        return ;
    }
    puts("Yes");
}
int main(){
    read();
    int t = read();
    while (t--) solve();
    return 0;
}