usaco_3_3_1_fence_欧拉回路.cpp

usaco自己做的1到5章的代码

/*
ID: wangyuc2
PROB:fence
LANG: C++
*/
/*
这道题，很经典的求欧拉回路的算法。
基本算法类似于DFS，根据性质，欧拉路径如果有奇度点那么起点一定是两个奇度点中的一个，否则任意偶度点为起点。
鉴于本题要求起始数字小，那么先从较小编号的点开始遍历，就不用排序了。
map[i][j]用来存储i和j之间的路径条数，deg[i]为顶点i的度，这样，每经过一条边，将这条边两个顶点的度减一，边也减一。
最后由于是递归得到的结果，所以path数组要逆序输出。
*/
#include <fstream>
#include <iostream>
#include <string>
#include <memory>
#include <algorithm>
#include <bitset>
#include <queue>
#include <vector>
#define MAXV 502
#define MAXE 1200
#define cin fin
using namespace std;

ifstream fin("fence.in");
ofstream fout("fence.out");
int map[MAXV][MAXV];
int deg[MAXV];
int path[MAXE];
int fn,minv,maxv,pathnum=0;
int init()
{
	int i,a,b;
	cin>>fn;
	memset(map,0,sizeof(map));
	memset(deg,0,sizeof(deg));
	memset(path,0,sizeof(path));
	minv=1200;
	maxv=0;
	for(i=0;i<fn;i++){
		cin>>a>>b;
		map[a][b]++;
		map[b][a]++;
		deg[a]++;
		deg[b]++;
		if(a>maxv) maxv=a;
		if(a<minv) minv=a;
		if(b>maxv) maxv=b;
		if(b<minv) minv=b;
	}
	return 0;
}
void find_path(int i)
{
	int j;
	for(j=minv;j<=maxv;j++)
		if(map[i][j]){
			map[i][j]--;
			map[j][i]--;
			deg[i]--;
			deg[j]--;
			find_path(j);
		}
	path[pathnum++]=i;
}
void output()
{
	for(int i=pathnum-1;i>=0;i--)
		fout<<path[i]<<endl;
}

int main()
{
	int i,j,k;
	init();
	for(i=minv;i<=maxv;i++) if(deg[i]%2==1) {k=i;break;}
	if(i>maxv) k=minv;
	find_path(k);
	output();
	return 0;
}