首页 > 代码库 > 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。