题目大意

• 给出一个n个点的有向图或无向图，要求输出其中一条欧拉回路 ( n<=100000 )

题解

• 听说有个叫环套环的算法，好像实现有点复杂，身为蒟蒻，能水就水
• 发现有向图和无向图各占50分
• 我们先可以将每个点的出度和入度都弄出来
• 对于无向图所有点的度都要是偶数，对于有向图入读必须等于出度
• 如果都满足，我们就随便从一个点出发，dfs找到一条欧拉回路就ok了

代码

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define N 100010 5 using namespace std; 6 int t,n,m,x,y,head[N],num,cnt=1,ans[N*2],in[N],out[N]; 7 bool vis[N*2]; 8 struct edge{
   int from,to;}e[N*4]; 9 void insert(int x,int y) { e[++cnt].to=y,e[cnt].from=head[x],head[x]=cnt; }10 void dfs(int x)11 {12     for (int &i=head[x];i;i=e[i].from)13     {14         int j=i;15         if (!vis[j>>1]) vis[j>>1]=1,dfs(e[i].to),ans[++num]=j;16     }17 }18 int main()19 {20     scanf("%d%d%d",&t,&n,&m);21     for (int i=1;i<=m;i++)22     {23         scanf("%d%d",&x,&y),insert(x,y);24         if (t==1) insert(y,x),in[x]++,in[y]++; else cnt++,in[y]++,out[x]++;25     }26     if (t==1)27     {28         for (int i=1;i<=n;i++) if ((in[i]+out[i])&1) { printf("NO"); return 0; }29     }30     else 31     {32         for (int i=1;i<=n;i++) if (in[i]!=out[i]) { printf("NO"); return 0; }33     }34     dfs(x);35     if (num!=m) printf("NO");36     else 37     {38         printf("YES\n");39         for (int i=num;i;i--) printf("%d ",ans[i]&1?-(ans[i]>>1):(ans[i]>>1));40     }41 }