欧拉图
欧拉图
2022.12.19~2023.1.5,2023.7.21
——整理于 Quack 的讲义
（附上一学长的论文）
一.定义
- 欧拉回路：通过图中每条边恰好一次的回路
- 欧拉通路：通过图中每条边恰好一次的通路
- 欧拉图：具有欧拉回路的图
- 半欧拉图：具有欧拉通路但不具有欧拉回路的图
二.判定
1.欧拉图判定
连通无向图：
- 所有点的度数是偶数
- 整个图可以被分解成若干环的并
连通有向图：
- 所有点的出度等于入度
- 整个图可以被分解成若干个有向的简单环的并
2.半欧拉图判定
连通无向图：
- 除了两个点的度数是奇数以外，所有点的度数是偶数
连通有向图：
- 起点终点出度入度分别差一，其余相等
三.求欧拉回路
题目：欧拉回路
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<limits.h>
using namespace std;
#define N 100005
#define M 400005
int t,n,m,u,v,in[N],ou[N],star=INT_MAX,ans[M],sum;
int head[N],cnt=1,to[M],nxt[M];//cnt初始化为1
bool vis[M];
void add(int u,int v){
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
void dfs(int u){
for(int &i=head[u];i;i=nxt[i]){//除去这里的取地址符,其他的与用链式前向星来遍历图一样
//取地址符：加上当前弧优化，遍历过的边就删除
//防止类似于两个点连多条边，每次遍历每一条边再判断的情况
int cur=i;
if(!vis[cur>>1]){
vis[cur>>1]=1;
dfs(to[cur]);
ans[++sum]=cur;
}
}
}
int main(){
scanf("%d %d %d",&t,&n,&m);//t=1:无向图;t=2:有向图;n:结点数;m:边数;
if(m==0){
printf("YES");
return 0;
}
for(int i=1;i<=m;i++){
scanf("%d %d",&u,&v);
add(u,v);
star=min(star,u);
star=min(star,v);//这是本题测试数据的需要,从不同的点开始得到的答案可能不一样
if(t==1){
add(v,u);
in[u]++,in[v]++;
}
else{
cnt++;//cnt为奇:u到v,边号为正;为偶:v到u,边号为负;
ou[u]++,in[v]++;
}
}
if(t==1){//无向图为欧拉图:每个点度数均为偶;
for(int i=1;i<=n;i++){
if(in[i]&1){
printf("NO");
return 0;
}
}
}
else{//有向图为欧拉图:每个点入度均等于出度
for(int i=1;i<=n;i++){
if(in[i]!=ou[i]){
printf("NO");
return 0;
}
}
}
dfs(star);
if(sum!=m){
printf("NO");
return 0;
}
printf("YES\n");
for(int i=sum;i;i--){//逆序输出
if(ans[i]&1)
printf("%d ",-(ans[i]>>1));
else
printf("%d ",(ans[i]>>1));
}
return 0;
} 四.习题
1.Trails and Glades
最少添加多少条边，使无向图有欧拉回路。
求出每个点的度数，奇数点需要连一条新边，仅有偶度数点的连通块需要连两条新边。
特判没有奇数点只有偶数点且只有一个连通块（已经成为欧拉回路）的情况，新边数为 0 。
答案为上面统计的新边数除以 2 。
坑点：
- 没有自环的孤立点不用连边，没有边相连的点可以不用到达
- 但是 1 必须到达，所以特定要访问 1
- 注意，自环不能直接删掉，孤立点的自环也要访问
2.无序字母对
给出 n 对需相邻的字符对，求一个字典序最小的字符串使得每对字符对都可在其中找到。
在给出的字符对的字符间连一条边，走一笔画（欧拉图）
3.太鼓达人
使 0~n 的二进制表示数都可在一个由0、1组成的字符串中找到。
4.丁香之路
由原题的边权可知，原题可转化成一条
考虑第
先让
还需联通。用并查集将已联通的联通块缩点。枚举未缩点的