POJ2230 Watchcow（打印欧拉回路）

电玩女神 2021-11-17 23:36 218阅读 0赞

## 题意：求无向图从起点1开始从不同方向经过所有边的一条路径，输出任意一条。 ##

## 分析：算是一个打印欧拉回路的板子题了，详见《算法竞赛进阶指南》P411-412。 ##

## 代码： ##

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int head[10010], ver[100010], Next[100010], tot; // 邻接表
    int stack[100010], ans[100010]; // 模拟系统栈，答案栈
    bool vis[100010];
    int n, m, top, t;
    
    void add(int x, int y) {
    	ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
    }
    
    void euler() {
    	stack[++top] = 1;
    	while (top > 0) {
    		int x = stack[top], i = head[x];
    		// 找到一条尚未访问的边
    		while (i && vis[i]) i = Next[i];
    		// 沿着这条边模拟递归过程，标记该边，并更新表头
    		if (i) {
    			stack[++top] = ver[i];
    			head[x] = Next[i];
    			// vis[i] = vis[i ^ 1] = true;
    		}
    		// 与x相连的所有边均已访问，模拟回溯过程，并记录
    		else {
    			top--;
    			ans[++t] = x;
    		}
    	}
    }
    
    int main() {
    	cin >> n >> m;
    	tot = 1;
    	for (int i = 1; i <= m; i++) {
    		int x, y;
    		scanf("%d%d", &x, &y);
    		add(x, y), add(y, x);
    	}
    	euler();
    	for (int i = t; i; i--) printf("%d\n", ans[i]);
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，218人围观）

还没有评论，来说两句吧...

相关阅读

相关欧拉通路欧拉回路的判定 Hdu 1878 欧拉回路

欧拉通路: 通过图中每条边且只通过一次，并且经过每一顶点的通路。欧拉回路: 通过图中每条边且只通过一次，并且经过每一顶点的回路。无向图是否具有欧拉通路或回路的判定:

矫情吗；*/ 2022年08月25日 09:16/ 0 赞/ 247 阅读

相关欧拉回路判断

//判断无向图是否是欧拉回路，欧拉回路：所有节点的度为偶数且连通 //使用并查集判断连通性 //题目：http://acm.hdu.edu.cn/sho

小咪咪/ 2022年07月15日 11:49/ 0 赞/ 252 阅读

相关欧拉回路欧拉通路的判定

欧拉通路: 通过图中每条边且只通过一次，并且经过每一顶点的通路。欧拉回路: 通过图中每条边且只通过一次，并且经过每一顶点的回路。无向图是否具有欧拉通路或回路的判定:

红太狼/ 2022年07月10日 23:57/ 0 赞/ 522 阅读

相关欧拉回路和欧拉道路

即一笔画问题。起点和终点相同称为回路，否则称为道路欧拉回路或道路存在判定无向图联通,有0个或2个奇点(度为奇数)。如果有两个奇点，则必须从一个奇点出发

墨蓝/ 2022年05月09日 05:36/ 0 赞/ 270 阅读

相关【UOJ117】欧拉回路（欧拉回路）

传送门 [UOJ][] Solution 无解 t=1，无向图，当且仅当\\(\\exists i \\ \\ in\_i \\ne out\_i\\

古城微笑少年丶/ 2022年01月09日 07:25/ 0 赞/ 305 阅读

相关欧拉回路与欧拉道路

欧拉回路与欧拉道路图G的一个[回路][Link 1]，若它恰通过G中每条边一次,则称该回路为欧拉(Euler)回路。如果一个图只是形成一个连通所有节点的链，且每一点只走

末蓝、/ 2021年12月23日 14:39/ 0 赞/ 387 阅读

相关 POJ2230 Watchcow（打印欧拉回路）

题意：求无向图从起点1开始从不同方向经过所有边的一条路径，输出任意一条。分析：算是一个打印欧拉回路的板子题了，详见《算法竞赛进阶指南》P411-412。代码：

电玩女神/ 2021年11月17日 23:36/ 0 赞/ 219 阅读

相关 [欧拉回路][dfs] Uoj #117 欧拉回路

题目大意给出一个n个点的有向图或无向图，要求输出其中一条欧拉回路 ( n<=100000 ) 题解听说有个叫环套环的算法，好像实现有点复杂，身为蒟

╰+哭是因爲堅強的太久メ/ 2021年11月02日 10:18/ 0 赞/ 363 阅读

相关欧拉路，欧拉回路

[欧拉路，欧拉回路][Link 1] 转载于:https://www.cnblogs.com/Al-Ca/p/11206978.html [Link 1]: https:

偏执的太偏执、/ 2021年10月26日 11:44/ 0 赞/ 388 阅读

相关欧拉回路欧拉通路欧拉回路图

[来源][Link 1] 一、定义对于无向图：　　1) 设G是连通无向图，则称经过G的每条边一次并且仅一次的路径为欧拉通路；　　2) 如果欧拉通路是回路（

灰太狼/ 2021年06月24日 15:57/ 0 赞/ 576 阅读