【Codeforces 521E】Cycling City | Mrsrz's blog

构造？

题目大意：

给定一张简单无向图，要求找到两个点 $u,v$，使得 $u$ 和 $v$ 之间存在三条不经过重复点（除了起点和终点外）的路径。输出方案或判断无解。

题解：

考虑先对原图进行 dfs 遍历，求出生成树。那么剩下的边一定都是返祖边。

我们令一条返祖边跨过的点称为被它包含的点。考虑两条返祖边，若被它们同时包含的点存在至少 $2$ 个，则我们找到一条方案。两个端点为同时包含的点的最深、最浅的点。

这个最深的点，就是两条返祖边较深一端的 LCA，而最浅的点，就是两条返祖边较浅一端中，深度较大的那个点。

所以输出方案也很好弄了。

Code：

#include<cstdio>
#include<cstdlib>
#include<vector>
const int N=2e5+6;
struct edge{
    int to,nxt;
    bool vis;
}e[N<<1];
int head[N],cnt=1,n,m,dep[N],fa[N],up[N];
bool vis[N];
std::vector<int>out;
void O_R(int now,const int&ed){
    if(now!=ed)O_R(fa[now],ed);
    out.push_back(now);
}
void output(){
    printf("%d",out.size());
    for(int i=0;i<out.size();++i)printf(" %d",out[i]);
    putchar('\n');
    out.clear();
}
void DFS(int now,int pre){
    vis[now]=1;
    for(int i=head[now];i;i=e[i].nxt)
    if(i!=pre&&!vis[e[i].to]){
        e[i].vis=1;
        dep[e[i].to]=dep[now]+1;
        fa[e[i].to]=now;
        DFS(e[i].to,i^1);
    }else
    if(dep[e[i].to]<dep[now]&&i!=pre){
        if(!up[now])up[now]=e[i].to;
        else{
            puts("YES");
            int u=up[now],v=e[i].to;
            if(dep[u]<dep[v])u^=v^=u^=v;
            out.push_back(now);
            for(int s=now;s!=u;s=fa[s])out.push_back(fa[s]);
            output();
            printf("2 %d %d\n",now,u);
            out.push_back(now);
            O_R(u,v);
            output();
            exit(0);
        }
    }
}
int dfs(int now){
    int res=up[now]?now:0;
    for(int i=head[now];i;i=e[i].nxt)
    if(e[i].vis){
        int t=dfs(e[i].to);
        if(up[t]==now)t=0;
        if(res&&t){
            int u=up[res],v=up[t];
            if(dep[u]<dep[v])u^=v^=u^=v,res^=t^=res^=t;
            puts("YES");
            O_R(res,now),out.push_back(u);
            output();
            out.push_back(now);
            for(int s=now;s!=u;s=fa[s])out.push_back(fa[s]);
            output();
            O_R(t,now),O_R(u,v);
            output();
            exit(0);
        }else if(t)res=t;
    }
    return res;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        e[++cnt]=(edge){v,head[u]},head[u]=cnt;
        e[++cnt]=(edge){u,head[v]},head[v]=cnt;
    }
    for(int i=1;i<=n;++i)if(!dep[i])dep[i]=1,DFS(i,0);
    for(int i=1;i<=n;++i)if(dep[i]==1)dfs(i);
    puts("NO");
    return 0;
}