这题要求一条路径走完所有的边并且不重复经过任意一条边...很典型的欧拉回路问题..关于欧拉回路本节的TXT就有介绍算法了...
首先一个连通的无向图如果所有的点度数位2存在欧拉回路(想象一个首尾相接的圈,如果两点间不止一条边,那么稍微变化下也能到所有点)...如果一个连通无向图有两个点的度为奇数也存在欧拉回路.并且这个回路一定是以这两点为起点终点的(想象一个直线...两端的度为1,中间的度都为2)...如果不止2个点的度为奇数..那么不存在欧拉回路..觉得这个还是很好想到和理解吧~
假设一个连通图存在欧拉回路...USACO提供的方法:(不完整的一部份..)
为何用这个方法能求出欧拉回路~~跟雄哥讨论了下说这实际上是一个作欧拉回路的逆过程...
PS: 最近又是CET又是期末考试的...生活都很混乱阿~~题也没A啥的说...本周五解脱~T_T...
Program:
/*
ID: zzyzzy12
LANG: C++
TASK: fence
*/
#include<iostream>
#include<istream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stack>
#include<algorithm>
#include<queue>
#define oo 1000000000
#define ll long long
using namespace std;
int F,arc[505][505],ans[1030],m,mm,a[505],t;
bool used[505];
stack<int> mystack;
void getanswer()
{
int i,h,num=F+1;
while (!mystack.empty()) mystack.pop();
memset(used,0,sizeof(used));
mystack.push(t);
while (!mystack.empty())
{
h=mystack.top();
if (!a[h])
{
ans[num]=h;
mystack.pop();
num--;
continue;
}
for (i=mm;i<=m;i++)
if (arc[i][h]) break;
a[h]--; a[i]--;
mystack.push(i);
arc[i][h]=--arc[h][i];
}
}
int main()
{
freopen("fence.in","r",stdin);
freopen("fence.out","w",stdout);
memset(arc,0,sizeof(arc));
scanf("%d",&F); m=0; mm=oo;
for (int i=1;i<=F;i++)
{
int x,y;
scanf("%d%d",&x,&y);
arc[x][y]=++arc[y][x];
if (x>m) m=x; if (y>m) m=y;
if (x<mm) mm=x; if (y<mm) mm=y;
a[x]++; a[y]++;
}
for (t=mm;t<=m;t++)
if (a[t]%2) break;
if (t==m+1) t=1;
getanswer();
for (t=1;t<=F+1;t++) printf("%d\n",ans[t]);
return 0;
}