UOJ #117. 欧拉回路
2018-06-17 21:08:17来源:未知 阅读 ()
#117. 欧拉回路
统计
有一天一位灵魂画师画了一张图,现在要你找出欧拉回路,即在图中找一个环使得每条边都在环上出现恰好一次。
一共两个子任务:
- 这张图是无向图。(50分)
- 这张图是有向图。(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。
- 如果 t=1t=1 则表示 vivi 到 uiui 有一条无向边。
- 如果 t=2t=2 则表示 vivi 到 uiui 有一条有向边。
图中可能有重边也可能有自环。
输出格式
如果不可以一笔画,输出一行 “NO”。
否则,输出一行 “YES”,接下来一行输出一组方案。
- 如果 t=1t=1,输出 mm 个整数 p1,p2,…,pmp1,p2,…,pm。令 e=∣pi∣e=∣pi∣,那么 ee 表示经过的第 ii 条边的编号。如果 pipi 为正数表示从 veve 走到 ueue,否则表示从 ueue 走到 veve。
- 如果 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; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:HDU1878 欧拉回路
- UOJ192 最强跳蚤 2020-02-05
- 「中山纪中集训省选组D2T1」书堆 欧拉常数 2019-08-16
- 欧拉函数 2018-10-03
- UOJ#386. 【UNR #3】鸽子固定器(链表) 2018-09-18
- UOJ#52. 【UR #4】元旦激光炮(交互) 2018-08-02
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash