欧拉回路-浅谈：专题

是什么

其实就是 一笔从起点经过所有边到达终点（欧拉路） 和 一笔从起点经过所有边回到起点（欧拉回路）

---

对于是否有回路的判定

1.无向图

结论

度数为偶数

证明

为了使形成回路，必定进入节点后，必须出去连接下一点（也就是说，进入节点多少次，就要出节点多少次）。
如果存在奇数条边，那么，必定总有一条边只可以进入节点而不可以出去和其他节点连接，就导致不可以构成回路。

2.有向图

结论

出度与入度相等

证明

同理，多少边进入，就要有多少边出去。

---

关于欧拉路径

和回路类似，无向图中，除原点（起点）和汇点（终点）是奇数条边，其余度数全都是偶数。

---

求欧拉回路&判断

原理

循环枚举找出发点。

具体步骤

1. 遍历到一点，加入路径
2. 找到子节点，入栈
3. 出栈，加入路径，删去刚刚走过的边
4. 判断栈是否为空，否-执行3，是-执行2
5. 所有边遍历完毕或无法再次遍历边，结束算法

---

例题

1. 洛谷P2731 骑马修栅栏 Riding the Fences
   模板，稍微改一下，原理一样
2. 洛谷P1341 无序字母对
   每两个字母连一条无向边，再求欧拉回路

洛谷P2731 骑马修栅栏 Riding the Fences

原题：传送门

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1031;
int n,m;
int a[maxn][maxn], du[maxn];

stack<int> S;

void dfs(int i){
    for(int j=1; j<=n; j++){
        if(a[i][j])
        {
            a[i][j]--;
            a[j][i]--;
            dfs(j);
        }
    }

    S.push(i);
}

int main(){
    cin>>m;
    int u,v;
    for(int i=1; i<=m; i++){
        cin>>u>>v;
        n = max(n,u);
        n = max(n,v);
        a[u][v]++;
        a[v][u]++;
        du[u]++;
        du[v]++;
    }
    int x = 1;
    for(int i=1; i<=n; i++){
        if(du[i]%2==1) {
            x=i;
            break;
        }
    }
    dfs(x);
    while(!S.empty()){
        cout<<S.top()<<endl;
        S.pop();
    }
    return 0;
}

洛谷P1341 无序字母对

原题：传送门

#include<bits/stdc++.h>
using namespace std;

const int maxn=2000;

int n;
int cnt,pos;

int e[maxn][maxn];
int du[maxn];
int lu[maxn];

int s=0x3f3f3f3f;


int pan(char x){
    if(x <= 'z' && x >= 'a'){
        return x - 'a' + 27;
    }
    else{
        return x - 'A' + 1;
    }
}
int pan2(char x){
    if(x <= 26){
        return 'A' + x - 1;
    }
    return 'a' + x - 27;
}
void dfs(int x){
    for(int y=1;y<=52;y++){
        if(e[x][y]==1){
            e[x][y]=e[y][x]=0;
            dfs(y);
        }
    }
    lu[++pos]=x;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        char x,y;
        cin>>x>>y;
        du[pan(x)]++,du[pan(y)]++;
        e[pan(x)][pan(y)]=e[pan(y)][pan(x)]=1;
    }
    for(int i=1;i<=52;i++){
        if(du[i]%2==1){
            s=min(s,i),cnt++;
        }
    }

    if(cnt!=0&&cnt!=2){
        cout<<"No Solution"<<endl;
        return 0;
    }

    if(cnt == 0){
        for(int i=1;i<=52;i++) if(du[i]) {
            s = i;
            break;
        }
    }

    dfs(s);

    for(int i=pos;i>=1;i--){
        cout<<(char)pan2(lu[i]);
    }


    return 0;
}

---

拜拜！安啦！ ︿(￣︶￣)︿

——End——