本文主要是介绍poj 1041 John's trip,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
典型的欧拉回路,先判断图的连通性,在统计每个点的度,无向图欧拉回路中不能存在度为奇数的节点,在递归输出字典序最小的一条路径。
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int edge[2000][2];
int degree[50],vis[2000],s[2000];
int edgenum,top,maxn,start,x,y,z;
bool check()
{
for(int i=1;i<=maxn;i++)
{
if(degree[i]%2)
return false;
}
return true;
}
void dfs(int m)
{
for(int i=1;i<=edgenum;i++)
{
if((m==edge[i][0]||m==edge[i][1])&&!vis[i])
{
vis[i]=1;
dfs(edge[i][0]+edge[i][1]-m);
s[top++]=i;
}
}
}
int main()
{
scanf("%d%d",&x,&y);
while(x&&y)
{
memset(vis,0,sizeof(vis));
memset(degree,0,sizeof(degree));
memset(edge,0,sizeof(edge));
maxn=edgenum=top=0;
start=min(x,y);
do{
scanf("%d",&z);
edge[z][0]=x;
edge[z][1]=y;
degree[x]++;
degree[y]++;
edgenum++;
maxn=max(maxn,max(x,y));
}while(scanf("%d%d",&x,&y)&&x&&y);
if(check())
{
dfs(start);
for(int i=top-1;i>=0;i--)
printf("%d ",s[i]);
printf("\n");
}
else
printf("Round trip does not exist.\n");
scanf("%d%d",&x,&y);
}
return 0;
}
这篇关于poj 1041 John's trip的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!