2023/6/10 学习笔记

oisoraku / 2023-06-11 / 原文

欧拉图

欧拉图的定义

欧拉回路:所有的边都经历一次不重复的回路

欧拉通路:所有的边都经历一次不重复的路径

欧拉图:具有欧拉回路的图

半欧拉图:具有欧拉通路的图

连通图只有0个或者偶数个奇数出度点

判别方法：

1.无向图欧拉回路:

(1)除去度为0的点外，其他的点相互连通

(2)顶点度数都是偶数

2.无向图欧拉通路:

(1)除去度为0的点外，其他的点相互连通

(1)具有0个或者偶数个奇数度顶点

3.有向图欧拉回路:

(1)非零度顶点是强连通图

(2)每个顶点的入度和出度数相同

4.有向图欧拉通路

(1)非零度顶点是弱连通图

(2)至多一个顶点的出度与入度之差为 1

(3)至多一个顶点的入度与出度之差为 1

(3)其他顶点的入度和出度相等

例题洛谷p1636

https://www.luogu.com.cn/problem/P1636

根据上面的无向图欧拉通路和连通图具有偶数个奇数度点，我们可以知道，两个奇数度点之间有一条欧拉通路，所以我们可以数奇数度点的个数，然后除以2就是我们要求的欧拉通路个数也即本题要求的笔画个数。

//code

#include<iostream>
#define maxm 100005
using namespace std;

int vis[maxm];

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int n,m,ant=0;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int u,v;
		cin>>u>>v;
		vis[u]++;
		vis[v]++;
	}
	for(int i=1;i<=n;i++){
		if(vis[i]%2!=0){
			ant++;
		}
	}
	if(ant==0){
		printf("1\n");
	}
	else{
		printf("%d\n",ant/2);
	}
	return 0;
}