首页 > 其他分享 >欧拉路和欧拉回路

欧拉路和欧拉回路

时间:2022-11-01 20:33:23浏览次数:70  
标签:int 出度 dfs ++ 回路 欧拉

定义

1.欧拉路:从图中一个点出发遍历整张图,每条边通过且只通过一次
2.欧拉回路:起点等于终点的欧拉路
3.偶点:度为偶数的点
4.奇点:度为奇数的点
5.考察内容:判断欧拉(回)路的存在,输出欧拉(回)路的路径

判断欧拉(回)路的存在

前提:判断连通性,dfs或者并查集。
无向图:图中所有点都是偶点,则存在欧拉回路,任一点均可以成为起点和终点;只有两个奇点,则存在欧拉路,其中一个奇点是起点,另一个奇点是终点
有向图:图中所有点入度和出度均相等,则存在欧拉回路;只有一个点入度比出度大1,只有一个点出度比入度大1,剩下的点出入度均相等,则存在欧拉路

输出欧拉回路

1.随便输出一条,直接从起点跑,用栈存路径。
2.输出字典序最小的欧拉回路,如果数据规模较小,可以用邻接矩阵。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, u, v, g[1005][1005];
int s[N], top;
void dfs(int u) {
	for (int i = 1; i <= n; i ++) {
		if (g[u][i]) {
			g[u][i] --;
			g[i][u] --;
			dfs(i);
		}
	}
	s[++ top] = u;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i ++) {
		cin >> u >> v;
		g[u][v] ++, g[v][u] ++;
	}
	dfs(1);
	while (top) cout << s[top --] << " ";
	return 0;
}

数据较大,就需要用类似打标记的方法标记边的遍历情况。
例题:P7771 【模板】欧拉路径

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, u, v, del[N];
int du[N][2];//0入度,1出度 
vector<int> e[N];
stack<int> st;//用于存路径 
void dfs(int u) {
	for (int i = del[u]; i < e[u].size(); i = del[u]) {
		del[u] = i + 1;
		//这样表示u这个点的前i条出边都遍历过了,下一次到u点时要从i+1条边开始 
		//一笔画问题,走过一条边删一条边 
		dfs(e[u][i]); 
	}
	st.push(u);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i ++) {
		cin >> u >> v;
		e[u].push_back(v);
		du[u][1] ++, du[v][0] ++;
	}
	//有字典序限制,用vector存图方便排序 
	for (int i = 1; i <= n; i ++) sort(e[i].begin(), e[i].end());
	int S = 1, cnt[2] = {0, 0};
	bool flag = 1;
	for (int i = 1; i <= n; i ++) {
		if (du[i][1] != du[i][0]) flag = 0;
		if (du[i][1] - du[i][0] == 1) cnt[1] ++, S = i;
		if (du[i][0] - du[i][1] == 1) cnt[0] ++; 
	}
	//欧拉回路和欧拉路径都不存在,输出No 
	if ((!flag) && !(cnt[0] == cnt[1] && cnt[0] == 1)) return !printf("No");
	dfs(S); //从起点开始
	while (!st.empty()) printf("%d ", st.top()), st.pop();//输出路径 
	return 0; 
}

image

标签:int,出度,dfs,++,回路,欧拉
From: https://www.cnblogs.com/YHxo/p/16849049.html

相关文章

  • 浅谈智能电表的预付费远程抄表及多回路监测系统设计及应用
    陈盼安科瑞电气股份有限公司上海嘉定201801【摘要】随着社会的发展,人工抄表这种费时费力、低效的工作模式将被淘汰,智能电表远程抄表系统应运而生。智能电表既能远程抄表,......
  • 【XSY4182】下一个(next)(欧拉回路,构造)
    题面下一个(next)题解我们可以这么转化问题:给每一条边定向,使得每一个点的出度至少为\(2\)。证明新问题是原问题的充分条件:定好向后,我们先给每个点随便选一条出边,显然这......
  • 【XSY3588】B(图论,欧拉回路)
    题意:给一张\(n\)个点\(m\)条边的简单连通无向图,保证\(m\)为偶数。可知度数为奇数的点共有偶数个,你需要将它们两两分组,对于每一组点\(u,v\),你要找到一条包含偶数条边......
  • 【bzoj4869】【六省联考2017】相逢是问候(扩展欧拉函数)
    和《花神游历各国》有异曲同工之妙。首先能想到扩展欧拉定理:\[a^b\equiv\begin{cases}a^{b\bmod\varphi(p)+\varphi(p)}&\text{if}b\geq\varphi(p)\\a^b&\text{if}......
  • 久违了!欧拉函数
    GCD-HDU2588-VirtualJudge(vjudge.net)题意:给定n,m,n<=1e9for(inti=1;i<=n;i++){if(gcd(i,n)>=m)cnt++;}注意到n<=1e9,这个模拟算法是不能通过的如......
  • 数论-欧拉函数 学习笔记
    一、欧拉函数1.欧拉函数的定义欧拉函数(Euler’stotientfunction),即,表示的是小于等于和比如说。当n是质数的时候,显然有。2.欧拉函数的一些性质欧拉函数是积性函数。......
  • 图论----欧拉路径与欧拉回路
    好博客:https://www.acwing.com/solution/content/53434/https://ycw123.blog.luogu.org/ou-la-hui-lu-yu-ou-la-lu-jing《介绍与性质》      对于无向图来......
  • 欧拉降幂
    放一张看烂的图欧拉降幂就是第一个和第三个公式了,第二种情况直接快速幂算当与模数互质时,当与模数不互质时,,这也就是广义欧拉定理适用于幂次很大时,可以有效降低复杂度在......
  • 欧拉函数积性性的证明
    若互质,则由互质可知无公因数,其中为的质因数,为的质因数,而无公因数所以互不相同,所以均为的质因数且为质因数的全集所以所以......
  • 欧拉定理相关性质及证明
    欧拉定理:当与互质时,有通项公式及其证明:如果,为质数,则证明:当一个数不包含质因子时就能与互质,小于等于的数中包含质因子p的只有个,即,把他们去除即可由唯一分解定理可知,这就是......