莲文化的魅力,超级博彩系统,外经贸在职研究生
有一天一位灵魂画师画了一张图,现在要你找出欧拉回路,即在图中找一个环使得每条边都在环上出现恰好一次。
一共两个子任务:
第一行一个整数 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。
图中可能有重边也可能有自环。
如果不可以一笔画,输出一行 “NO”。
否则,输出一行 “YES”,接下来一行输出一组方案。
1 3 3 1 2 2 3 1 3
YES 1 2 -3
2 5 6 2 3 2 5 3 4 1 2 4 2 5 1
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; }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论