【AtCoder Grand Contest 032 C】Three Circuits | Mrsrz's blog

构造。

题目大意：

给定一张无向连通图，问能否找到三条回路，使得三条回路的边集的交为空，且边集的并为所有边。

题解：

由于要把原图拆成三条回路，且原图连通，所以原图本身一定能形成回路，故所有顶点的度数必须是偶数。

考虑度数最大的顶点的度数。

若最大为 $2$，则只能是单个环，不存在方案。

若最大超过 $4$，则这个度数最大的点出发，一定能连至少三个环，必定存在方案。

若最大为 $4$，并且这样的点超过 $2$ 个，则一定可以（考虑一个结点所在的两个子回路）。

若最大为 $4$，并且这样的点只有 $1$ 个，则一定不行。

若最大为 $4$，并且这样的点恰好两个，则分两种情况：

1. 这两个四度顶点同时在两个不同环上。那么去掉这两个环就没有其他环了，不行。
2. 这两个四度顶点在一个环上，且另外各自在另一个环上。那么是可以的。

在判上面这个情况的时候，可以去掉其中一个四度顶点，然后判断剩下的点能否形成环即可。

Code：

#include<cstdio>
#include<algorithm>
const int N=1e5+6;
int n,m,deg[N],u,v,head[N],cnt=1;
bool vis[N];
struct edge{
    int to,nxt;
}e[N<<1];
void dfs(int u,int pre){
    vis[u]=1;
    for(int i=head[u];i;i=e[i].nxt)
    if(i!=pre&&e[i].to!=v){
        if(!vis[e[i].to])dfs(e[i].to,i^1);else{puts("Yes");exit(0);}
    }
    vis[u]=0;
}
int main(){
    scanf("%d%d",&n,&m);
    while(m--){
        scanf("%d%d",&u,&v);
        e[++cnt]=(edge){v,head[u]},head[u]=cnt;
        e[++cnt]=(edge){u,head[v]},head[v]=cnt;
        ++deg[u],++deg[v];
    }
    for(int i=1;i<=n;++i)if(deg[i]&1)return puts("No"),0;
    if(*std::max_element(deg+1,deg+n+1)>4)return puts("Yes"),0;
    u=v=0;
    for(int i=1;i<=n;++i)
    if(deg[i]==4){if(!u)u=i;else if(!v)v=i;else return puts("Yes"),0;}
    if(v)dfs(u,0);
    return puts("No"),0;
}