UOJ #117. 欧拉回路

2018-03-01 12:21:52来源:cnblogs.com作者:自为风月马前卒人点击

分享

#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

13 31 22 31 3

output

YES1 2 -3

样例二

input

25 62 32 53 41 24 25 1

output

YES4 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;}

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台