首页 > 代码库 > POJ 2230 Watchcow 欧拉回路题解

POJ 2230 Watchcow 欧拉回路题解

本题就是以每个节点和节点之间建路,而且说明是无向图,不过这里有个技巧,就是根据题意把它当成有向图来做,就成了直接查找有向图的欧拉回路就可以了。因为题意是需要每条边都走两遍的,而且每次走的方向相反。

观察出这点,那么这道题就好做啦,直接建图,Feury递归求解就可以了。

建图注意需要建邻接表,不要建矩阵,因为建成矩阵,那么会很大很大,而根据题意,建成邻接表最多只需要5倍的顶点数。

打印的顺序是逆过来打和顺着打都可以的,因为先走那边都可以。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
using namespace std;

const int MAX_VEC = 10001;
vector<int> trails[MAX_VEC];
vector<int> paths;
int N, M;

void Feury(int v)
{
	for (int i = 0; i < (int)trails[v].size(); i++)
	{
		if (trails[v][i])
		{
			int des = trails[v][i];
			trails[v][i] = 0;
			Feury(des);
		}
	}
	paths.push_back(v);
}

int main()
{
	int u, v;
	while (scanf("%d %d", &N, &M) != EOF)
	{
		for (int i = 1; i <= N; i++)
			trails[i].clear();
		paths.clear();

		for (int i = 0; i < M; i++)
		{
			scanf("%d %d", &u, &v);
			trails[u].push_back(v);
			trails[v].push_back(u);
		}

		Feury(1);
		for (int i = (int)paths.size() - 1; i >= 0; i--)
		{
			printf("%d\n", paths[i]);
		}
	}
	return 0;
}