首页 > 代码库 > poj1041欧拉回路
poj1041欧拉回路
#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <cmath>#include <stack>#include <queue>#include <vector>#include <map>#include <string>#include <iostream>using namespace std;const int maxn=2000;int len;int head[maxn];struct Node{ int a;int b;int c;}node[maxn];struct edge{ int to;int val;int next;int op;int vis;}e[maxn*maxn];int add(int from,int to,int val){ e[len].to=to; e[len].val=val; e[len].next=head[from]; head[from]=len++; return len-1;}int n=0;int sum;int cmp(const Node &a,const Node &b){ return a.c<b.c;}void dfs(int u){ for(int i=head[u];i!=-1;i=e[i].next){ if(!e[i].vis){ e[i].vis=1;e[e[i].op].vis=1; int cc=e[i].to; dfs(cc); cout<<e[i].val<<" "; } }}int main(){ int a;int b;int c; int degree[maxn]; while(scanf("%d%d",&a,&b),a||b){ memset(degree,0,sizeof(degree)); len=0; memset(head,-1,sizeof(head)); sum=0; scanf("%d",&c); node[sum].a=a;node[sum].b=b;node[sum].c=c; sum++;if(a>n) n=a;if(b>n) b=n; while(scanf("%d%d",&a,&b),a||b){ scanf("%d",&c);node[sum].a=a;node[sum].b=b;node[sum].c=c; sum++;if(a>n) n=a;if(b>n) n=b; } sort(node,node+sum,cmp); for(int i=0;i<sum;i++){ int a=node[i].a;int b=node[i].b;int c=node[i].c; int cc=add(a,b,c);int cc1=add(b,a,c); degree[a]++;degree[b]++; e[cc].op=cc1;e[cc1].op=cc; e[cc].vis=e[cc1].vis=0; } int flag=0; for(int i=0;i<sum;i++){ int a=node[i].a;int b=node[i].b; if((degree[a]&1)||(degree[b]&1)) { flag=1;break; } } if(!flag){ dfs(1); } else cout<<"Round trip does not exist."; cout<<endl; } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。