UOJ117. 欧拉回路【欧拉回路】

#117. 欧拉回路

【题目描述】

传送门

【题解】

欧拉回路裸题。DFS时要优化。

代码如下

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXN=1e5+5,MAXE=2e5+5;
int n,m,typ,stk[MAXE],Top,vis[MAXE];
struct Edge{
    int tot,lnk[MAXN],D[MAXN],nxt[MAXE<<1],son[MAXE<<1];
    void clear(){memset(lnk,-1,sizeof(lnk));tot=-1;}
    void Add(int x,int y){D[x]++,D[y]-=typ;nxt[++tot]=lnk[x];lnk[x]=tot;son[tot]=y;}
}E;
void DFS(int x){
    for(int j=E.lnk[x];j^-1;j=E.lnk[x]){
        E.lnk[x]=E.nxt[j];
        if(!typ){if(vis[j>>1]) continue;vis[j>>1]=1;DFS(E.son[j]),stk[++Top]=((j>>1)+1)*(j&1?-1:1);}
        else{if(vis[j]) continue;vis[j]=1;DFS(E.son[j]),stk[++Top]=j+1;}
    }
}
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret<<3)+(ret<<1)+ch-48;
    return f?ret:-ret;
}
int main(){
    typ=read()-1;E.clear();
    n=read(),m=read();
    for(int i=1,x,y;i<=m;i++){x=read(),y=read(),E.Add(x,y);if(!typ) E.Add(y,x);}
    if(typ) for(int i=1;i<=n;i++){if(E.D[i]) return printf("NO\n"),0;}
    else for(int i=1;i<=n;i++){if(E.D[i]&1) return printf("NO\n"),0;}
    for(int i=1;i<=n;i++) if(E.lnk[i]>-1){DFS(i);break;}
    if(Top!=m) return puts("NO"),0;
    puts("YES");
    for(;Top;Top--) printf("%d ",stk[Top]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部