欧拉回路

https://loj.ac/problem/10105

题目描述

  两个任务：(t=1)时，求无向图是否存在欧拉回路及其方案；(t=2)时，求有向图是否存在欧拉回路及其方案。

思路

  对于无向图，存在欧拉回路的条件是所有节点的度均为偶数；对于有向图，存在欧拉回路的条件是原图的基图（忽略原图边方向的图）连通，且所有节点的如度等于出度。接下来考虑如何求一条欧拉回路。

  我们考虑一条欧拉回路必定是由几个简单环构成的，所以我们直接沿每条边走，如果走成一条环就不再走这条边，从其他变开始走，最后合并起来的环就一定是欧拉回路的一种方案。因此对于任意一个点开始(dfs)即可。不过由于我们会重复访问很多次同一节点，时间复杂度可能会变为(O（N×M）)，所以我们考虑走过这条边就把这条边删去，代码实现时在(i=head[u])改为(i=)&(head[u])即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=4e5+10;

void end()
{
    printf("NO");
    exit(0);
}

int nxt[M],to[M],tot=1,head[N];
void add_edge(int x,int y)
{
    nxt[++tot]=head[x];
    head[x]=tot;
    to[tot]=y;
}

int read()
{
    int res=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+ch-'0';ch=getchar();}
    return res*w;
}

int t;
vector<int>ans;
bool vis[M];
void dfs(int u)
{
//    cout<<u<<':'<<endl;
    for(int &i=head[u];i;i=nxt[i])
    {
        int v=to[i],c=((t==1)?i/2:i-1),f=i&1;
        if(vis[c])continue ;
        vis[c]=1;
        dfs(v);
        if(t==1)ans.push_back(f?-c:c);
        else ans.push_back(c);
    }    
}

int in[N],out[N];
int main() 
{
    int n,m;
    t=read();
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        add_edge(x,y);
        if(t==1)add_edge(y,x);
        in[y]++;out[x]++;
    }
    if(t==1)
    {
        for(int i=1;i<=n;i++)
            if((in[i]+out[i])%2)end();
    }
    else
    {
        for(int i=1;i<=n;i++)
            if(in[i]!=out[i])end();
    }
    for(int i=1;i<=n;i++)
        if(head[i])
        {
            dfs(i);
            break ;
        }
//    cout<<ans.size()<<endl;
    if(ans.size()!=m)end();
    printf("YES
");
    for(int i=m-1;i>=0;i--)
        printf("%d ",ans[i]);
}