#117. 歐拉迴路

 統計

•  描述
•  提交
•  自定義測試

有一天一位靈魂畫師畫了一張圖，現在要你找出歐拉迴路，即在圖中找一個環使得每條邊都在環上出現恰好一次。

一共兩個子任務：

1. 這張圖是無向圖。（50分）
2. 這張圖是有向圖。（50分）

輸入格式

第一行一個整數 tt，表示子任務編號。t∈{1,2}t∈{1,2}，如果 t=1t=1 則表示處理無向圖的情況，如果 t=2t=2 則表示處理有向圖的情況。

第二行兩個整數 n,mn,m，表示圖的結點數和邊數。

接下來 mm 行中，第 ii 行兩個整數 vi,uivi,ui，表示第 ii 條邊（從 11 開始編號）。保證 1≤vi,ui≤n1≤vi,ui≤n。

1. 如果 t=1t=1 則表示 vivi 到 uiui 有一條無向邊。
2. 如果 t=2t=2 則表示 vivi 到 uiui 有一條有向邊。

圖中可能有重邊也可能有自環。

輸出格式

如果不可以一筆畫，輸出一行 “NO”。

否則，輸出一行 “YES”，接下來一行輸出一組方案。

1. 如果 t=1t=1，輸出 mm 個整數 p1,p2,…,pmp1,p2,…,pm。令 e=∣pi∣e=∣pi∣，那麼 ee 表示經過的第 ii 條邊的編號。如果 pipi 為正數表示從 veve 走到 ueue，否則表示從 ueue 走到 veve。
2. 如果 t=2t=2，輸出 mm 個整數 p1,p2,…,pmp1,p2,…,pm。其中 pipi 表示經過的第 ii 條邊的編號。

樣例一

input

1
3 3
1 2
2 3
1 3

output

YES
1 2 -3

樣例二

input

2
5 6
2 3
2 5
3 4
1 2
4 2
5 1

output

YES
4 1 3 5 2 6

限制與約定

1≤n≤105,0≤m≤2×1051≤n≤105,0≤m≤2×105

時間限制：1s1s

空間限制：256MB256MB

下載

當圖是無向圖時，歐拉迴路的存在條件為所有點的入度為偶數

當圖是有向圖時，歐拉迴路的存在條件是所有點的入度等於出度

求歐拉迴路時dfs所有邊

回溯時存下所有邊

然後倒敘輸出

UOJ的數據真是坑，自環重邊漫天飛QWQ、、、

還有GG();寫成GG;居然不報錯QWQ。、

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int MAXN=1e6+10;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20+1,stdin),p1==p2)?EOF:*p1++)
char buf[1<<20+1],*p1=buf,*p2=buf;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int N,M,S;
struct node
{
    int u,v,ID,nxt;
}edge[MAXN];
int head[MAXN],num=1;
int inder[MAXN],ans[MAXN],vis[MAXN],tot=0;
inline void AddEdge(int x,int y,int z)
{
    edge[num].u=x;
    edge[num].v=y;
    edge[num].ID=z;
    edge[num].nxt=head[x];
    head[x]=num++;
}
void GG(){printf("NO");exit(0);}
int dfs(int now)
{
    for(int i=head[now];i!=-1;i=edge[i].nxt)
    {
        if(!vis[abs(edge[i].ID)])
        {
            head[now]=i;
            vis[abs(edge[i].ID)]=1,dfs(edge[i].v);
            ans[++tot]=edge[i].ID;
            i=head[now];    
        }
    }
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    memset(head,-1,sizeof(head));
    int QWQ=read();
    if(QWQ==1)
    {
        N=read();M=read();
        for(int i=1;i<=M;i++)
        {
            int x=read(),y=read();S=x;
            AddEdge(x,y,i);
            AddEdge(y,x,-i);
            inder[x]++;inder[y]++;
        }
        for(int i=1;i<=N;i++)
            if(inder[i]&1) GG();
        dfs(S);
        if(tot<M) GG();
        puts("YES");
        for(int i=M;i>=1;i--)
            printf("%d ",ans[i]);
    }
    else
    {
        N=read();M=read();
        for(int i=1;i<=M;i++)
        {
            int x=read(),y=read();S=x;
            AddEdge(x,y,i);
            inder[y]--;inder[x]++;
            S=x;
        }
        for(int i=1;i<=N;i++)
            if(inder[i]!=0)
                GG();
        dfs(S);
        if(tot<M) GG();
        puts("YES");
        for(int i=M;i>=1;i--)
            printf("%d ",ans[i]);
    }
    return 0;
}