欧拉路径

· · 个人记录

欧拉路径

定义

1.通过图中所有边恰好一次的通路称为欧拉通路。

2.通过图中所有边恰好一次的回路称为欧拉回路。

3.具有欧拉回路的无向图或有向图称为欧拉图。

4.具有欧拉通路但不具有欧拉回路的无向图或有向图称为半欧拉图。

5.欧拉图从任意一个点开始都可以一笔画完整个图，半欧拉图必须从某个点开始才能一笔画完整个图。

性质：

定理1：无向欧拉图中所有顶点的度数都是偶数

推论1：无向半欧拉图只有两个顶点的度数为奇数

定理2：有向欧拉图的所有顶点的入度=出度

推论2：有向半欧拉图只存在1个点入比出大1，1个点出比入大1

定理3：一个欧拉图是几个环的并集，每一条边都在奇数个环里

性质：C1，C2是两个没公共边但有公共点的回路，则可以合并成一个新回路C'

算法操作

例：P7771 【模板】欧拉路径

做法1：朴素删边
从一个点出发（字典序最小从1开始）查找出边
移动到终点，把该出边标记，从终点继续遍历
在回溯的时候把起点入栈，使点的栈倒序
存在则最后出栈输出
//不是AC做法!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
#include<bits/stdc++.h>
using namespace std;
struct node{int to,next;}bian[200010];
int n,m,cnt,head[200010],sum;bool flag;
void add(int x,int y){
    cnt++;
    bian[cnt].to=y;
    bian[cnt].next=head[x];
    head[x]=cnt;
}
int vis[200010],zhan[200010],tou;
void push(int x){zhan[tou++]=x;}//栈 
int pop(){return zhan[--tou];}//栈 
void dfs(int now){ 
    for(int k=head[now];k;k=bian[k].next){//找到当前节点的出边 
        if(vis[k]==0){//如果没有被标记 
            vis[k]=1;//标记 
            sum++;
            dfs(bian[k].to);//向下递归
        }
    }
    push(now);//把当前节点入栈 
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        add(u,v);
    }
    dfs(1);
    while(tou!=0)
        cout<<pop()<<' ';
    return 0;
}
#include<bits/stdc++.h>
using namespace std;
struct node{int to,next;}bian[100010];
int n,m,cnt,head[100010];
int stk[100010],top;//系统栈，系统栈顶
int ans[100010],tot;//答案栈，答案栈顶
//系统栈负责模拟递归，答案栈负责存储节点形成回路序列
bool vis[100010];//删边 
void add(int x,int y){
    cnt++;
    bian[cnt].to=y;
    bian[cnt].next=head[x];
    head[x]=cnt;
} 
void euler(){
    stk[++top]=1;
    while(top>0){//模拟递归 
        int x=stk[top];int i=head[x];//从栈首出发找边
        while(i&&vis[i])i=bian[i].next;//一直向下查找直到找到一条没被访问的边
        if(i){//从这条边开始模拟递归过程，标记同时更新head以便再次遍历到x时直接查找到这条没被访问的边
            stk[++top]=bian[i].to;//终点入栈
            head[x]=bian[i].next;//更新i的next减少边的遍历次数
            vis[i]=vis[i^1]=true;
        }
        else{//与x相连的出边都已经被访问，开始回溯同时记录答案 
            top--;ans[++tot]=x; 
        }
    } 
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;//u->v
        add(u,v); 
    }
    euler();//模拟递归
    for(int i=tot;i;i--)cout<<ans[i]<<' '; 
    return 0;
}