CF36 E Two Paths——欧拉(回)路

时间：2021-01-17 15:31:35

题目：http://codeforces.com/contest/36/problem/E

给定一张无向图，要求输出两条欧拉路覆盖所有边；

分类讨论，首先判-1：有两个以上连通块 / 有四个以上奇度数点 / 只有一条边 / 有两个连通块而其中一个连通块里有四个奇度数点 (/ 有连通块里有奇数个奇度数点)；

然后分两个连通块和一个连通块的情况进行 dfs 找欧拉路(模板 dfs )；

注意可能没有奇度数的点，也就是有欧拉回路，所以不仅找奇度数点进行 dfs ，还要在那之后 dfs 仍然没有被走过的点；

明明是模仿题解写的竟然还调了两小时...码力++...

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int const maxn=;

int n,m,d[maxn],ans[maxn],tot,fa[maxn],cnt,c[maxn],hd[maxn],ct=;

bool vis[maxn],used[maxn];

struct N{

    int to,nxt;

    N(int t=,int n=):to(t),nxt(n) {}

}ed[maxn<<];

void add(int x,int y){ed[++ct]=N(y,hd[x]); hd[x]=ct;}

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

void dfs(int x)

{

    vis[x]=;

    for(int i=hd[x];i;i=hd[x])

    {

        hd[x]=ed[i].nxt;

        if(used[i>>])continue;

        used[i>>]=; dfs(ed[i].to); ans[++tot]=(i>>);

    }

}

int main()

{

    freopen("input.txt","r",stdin);

    freopen("output.txt","w",stdout);

    n=; scanf("%d",&m);//不能是 n=10005

    for(int i=;i<=n;i++)fa[i]=i;//!!

    for(int i=,x,y;i<=m;i++)

    {

        scanf("%d%d",&x,&y);

        add(x,y); add(y,x); d[x]++; d[y]++;

        if(find(x)!=find(y))fa[find(x)]=find(y);

    }

    for(int i=;i<=n;i++) if(d[i]&) c[find(i)]++;

    for(int i=;i<=n;i++) if(c[i]&){printf("-1\n"); return ;}

    for(int i=,sum=;i<=n;i++)

    {

        if(d[i])cnt+=(i==find(i));

        if(c[i])sum+=c[i];

        if(sum>){printf("-1\n"); return ;}

    }

    if(cnt>){printf("-1\n"); return ;}

    if(cnt==)

    {

        for(int i=;i<=n;i++) if(c[i]==){printf("-1\n"); return ;}

        for(int i=;i<=n;i++)

            if(!vis[i]&&(d[i]&))

            {

                tot=; dfs(i); printf("%d\n",tot);

                for(int j=tot;j;j--)printf("%d ",ans[j]); printf("\n");

            }

        for(int i=;i<=n;i++)//欧拉回路

            if(!vis[i]&&d[i])

            {

                tot=; dfs(i); printf("%d\n",tot);

                for(int j=tot;j;j--)printf("%d ",ans[j]); printf("\n");

            }

    }

    else

    {

        bool fl=;

        for(int i=;i<=n;i++) if(c[i]==)fl=;

        if(fl)

        {

            for(int i=;i<=n;i++)    if(d[i]&)

            {

                for(int j=i+;j<=n;j++)

                    if(d[j]&){d[i]++; d[j]++; add(i,j); add(j,i); break;}

                break;

            }

            for(int i=;i<=n;i++)

                if(!vis[i]&&(d[i]&)){tot=; dfs(i); break;}

            for(int i=;i<=tot;i++)    if(ans[i]==m+)

            {

                printf("%d\n",i-);

                for(int j=;j<i;j++)printf("%d ",ans[j]); printf("\n");

                printf("%d\n",tot-i);

                for(int j=i+;j<=tot;j++)printf("%d ",ans[j]);

                break;

            }

        }

        else

        {

            for(int i=;i<=n;i++)

                if(!vis[i]&&(d[i]&)){tot=; dfs(i);}

            for(int i=;i<=n;i++)//欧拉回路

                if(!vis[i]&&d[i]){tot=; dfs(i);}

            if(tot<=){printf("-1\n"); return ;}//只有一条边

            printf("1\n%d\n%d\n",ans[],tot-);

            for(int i=;i<=tot;i++)printf("%d ",ans[i]);

        }

    }

    return ;

}

相关文章