欧拉图——Euler Graph

1.欧拉图定义

1. 欧拉通路
   我们从有向图和无向图中的任意一点出发，将所有的边遍历且仅遍历一遍的通路序列我们称为欧拉通路
2. 欧拉回路
   如果欧拉通路的起点和终点是一样的，我们称之为欧拉回路
3. 欧拉图
   具有欧拉回路的图称之为欧拉图，规定只有一个定点的空图（平凡图）属于欧拉图
4. 半欧拉图
   具有欧拉通路的图我们称之为半欧拉图

2.欧拉图应用

例题：一笔画问题（南阳OJ42题）

描述

zyc从小就比较喜欢玩一些小游戏，其中就包括画一笔画，他想请你帮他写一个程序，判断一个图是否能够用一笔画下来。
规定，所有的边都只能画一次，不能重复画。

输入

第一行只有一个正整数N(N<=10)表示测试数据的组数。
每组测试数据的第一行有两个正整数P,Q(P<=1000,Q<=2000)，分别表示这个画中有多少个顶点和多少条连线。（点的编号从1到P）
随后的Q行，每行有两个正整数A,B(0 < A,B < P)，表示编号为A和B的两点之间有连线。

输出

如果存在符合条件的连线，则输出”Yes”,
如果不存在符合条件的连线，输出”No”。

样例输入

2
4 3
1 2
1 3
1 4
4 5
1 2
2 3
1 3
1 4
3 4

样例输出

No
Yes

题解：

此题就是一个欧拉图应用的模板题。但是，因为在做这题之前，我暂未接触到欧拉图（太渣。。），所以，用DFS解决了这个问题。题目AC之后，看了题目的讨论板。发现了这个欧拉图的存在。于是我又用欧拉图写了一遍。AC之后，我比较了两者的特点，发现欧拉图方法（判连通 + 判断节点度的奇偶性）明显时间上优化了很多。

| 结果 | 时间 | 内存 | 语言 | 方法 |
| ————- |:————-? —–?
| Accepted | 4 | 8724 | C/C++ |欧拉图|
| Accepted | 734 | 8852 | C/C++ |普通DFS|

此题就是找欧拉通路or欧拉回路，一个图如果能够一笔画，那必定存在欧拉通路或者欧拉回路。所以，该图必定是一个连通图。又因为从某个点进去，必定会从该点出来，所以度为奇数的点的个数应该0个或者2个。当为0个时，图中存在欧拉回路（起点终点相同）; 当为2个时，图中存在欧拉通路（起点终点不相同）。

代码：

欧拉图AC代码：

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 10005;
int n;
int father[N];
int point , edge;
int in[N];
//使用并查集来判连通
int find(int a){    //并查集的查
    int x = a;
    while(x != father[x]){
        x = father[x];
    }
    int i = a , j;
    while(i != x){
        j = father[i];
        father[i] = x;
        i = j;
    }
    return x;
}

void set(int a , int b){    //并查集的并
    int father1 = find(a);
    int father2 = find(b);
    if(father1 != father2){
        father[b] = a;
    }
}

int main(){
    cin >> n;
    while(n--){
        cin >> point >> edge;
        if(point == 1){ //平凡图特判
            cout << "Yes" << endl;
            continue;
        }
        for(int i = 1;i < N;i++){
            father[i] = i;
            in[i] = 0;
        }
        int from , to;
        for(int i = 0;i < edge;i++){
            cin >> from >> to;
            set(from , to); //往并查集里面插入
            in[from]++; //计算点的度
            in[to]++;
        }
        bool flag = false;
        int cnt1 = 0 , cnt2 = 0;
        for(int i = 1;i <= point;i++){
            if(in[i] & 1) cnt1++;   //统计度为奇数的点的个数
            if(father[i] == i) cnt2++;  //统计父节点的个数
        }
        // 如果父节点的个数为1,表明图连通;
        // 如果度为奇数的点的个数为0或者2的话，
        // 说明图中必定存在欧拉回路或者欧拉通路，满足了题目要求，输出"Yes"
        if((cnt1 == 0 || cnt1 == 2) && cnt2 == 1)   
            cout << "Yes" << endl;
        else   
            cout << "No" << endl;        
    }
    return 0;
}