本题就是以每个节点和节点之间建路,而且说明是无向图,不过这里有个技巧,就是根据题意把它当成有向图来做,就成了直接查找有向图的欧拉回路就可以了。因为题意是需要每条边都走两遍的,而且每次走的方向相反。
观察出这点,那么这道题就好做啦,直接建图,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; }
POJ 2230 Watchcow 欧拉回路题解,布布扣,bubuko.com
原文:http://blog.csdn.net/kenden23/article/details/34854057