首页 > 代码库 > UVA10054_The Necklace
UVA10054_The Necklace
很简单,求欧拉回路。并且输出。
只重点说一下要用栈来控制输出。
为啥,如图:
如果不用栈,那么1->2->3->1就回来了,接着又输出4->5,发现这根本连接不上去,所以如果用栈的话,就会保存一条完整的路径咯。
因为是无向图,只要满足每个点的度数都是偶数的话就一定存在合法的欧拉回路了。
召唤代码君:
#include <iostream>#include <cstring>#include <cstdio>using namespace std;int a[51][51],n=50,d[51],m,T;void dfs(int x){ for (int i=1; i<=n; i++) if (a[x][i]) { a[x][i]--,a[i][x]--; dfs(i); printf("%d %d\n",i,x); }}int main(){ int cas=0,U,V; scanf("%d",&T); while (T--) { memset(d,0,sizeof d); memset(a,0,sizeof a); scanf("%d",&m); while (m--) { scanf("%d%d",&U,&V); a[U][V]++,a[V][U]++; d[U]++,d[V]++; } bool ans=true; for (int i=1; i<=n; i++) if (d[i]&1) ans=false; if (cas) printf("\n"); printf("Case #%d\n",++cas); if (!ans) printf("some beads may be lost\n"); else dfs(U); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。