欧拉通路，欧拉回路¶

欧拉通路: 通过图中每条边且只通过一次，并且经过每一顶点的通路

欧拉回路: 通过图中每条边且只通过一次，并且经过每一顶点的回路

有向图的基图：忽略有向图所有边的方向，得到的无向图称为该有向图的基图。

无向图¶

G是连通无向图，则称经过G的每条边一次并且仅一次的路径为欧拉通路；
如果欧拉通路是回路（起点和终点是同一个顶点），则称此回路是欧拉回路
具有欧拉回路的无向图G成为欧拉图

定理

无向图G存在欧拉通路的充要条件是：G为连通图，并且G仅有两个奇度结点（度数为奇数的顶点）或者无奇度结点。

推论

（1）当G是仅有两个奇度结点的连通图时，G的欧拉通路必以此两个结点为端点；

（2）当G是无奇度结点的连通图时，G必有欧拉回路

（3）G为欧拉图（存在欧拉回路）的充分必要条件是 G为无奇度结点的连通图

有向图¶

（1）设D是有向图，D的基图连通，则称经过D的每条边一次并且仅有一次的有向路径为有向欧拉通路

（2）如果有向欧拉通路是有向回路，则称此有向回路为有向欧拉回路

（3）具有有向欧拉回路的图D称为有向欧拉图

（有向图）定理

有向图D存在欧拉通路的充要条件是：D为有向图，D的基图连通，并且所有顶点的出度与入度相等；或者除两个顶点外，其余顶点的出度与入度都相等，而这两个顶点中一个顶点的出度与入度之差为1，另一个顶点的出度与入度之差为-1.

推论

（1）当D除出、入度之差为1，-1的两个顶点之外，其余顶点的出度与入度相等时，D的有向欧拉通路必以出、入度之差为1的顶点作为始点，以出、入度之差为-1的顶点作为终点。

（2）当D的所有顶点的出、入度都相等时，D中存在有向欧拉回路。

（3）有向图D为有向欧拉图的充要条件是 D的基图为连通图，并且所有顶点的出、入度都相等。

求解欧拉回路通过dfs或并查集求解¶

UVA-10054

题意：有一堆珠子，每个珠子有两个颜色，我们需要从中找出来一些珠子把它穿成一串，每两个珠子相对的颜色相同我们把每个珠子看整一个边，两个颜色看成节点，就是看看给定的边又没有欧拉回路既然问你有无欧拉回路那就欧拉定理判断有没有度数为奇数的点（如果是寻找欧拉通路的话需要两个或没有奇数度的点）如果全为偶数度的点，就肯定有欧拉回路，直接爆搜就可以了，注意会又重边的情况，然后因为你也不知道1-50之内的那个点在图内使用，所以我们直接全搜一下，搜完一定是所有的点都用完了所以不会再搜了。（最后for循环的解释因为是一条路一路搜下去就可以了所以不用考虑回溯的vis问题，然后也不要考虑存路径，回溯是输出就好了

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 105;
int n;
int g[maxn][maxn];

int d[maxn];

int st,flag=0;
void dfs(int u){
    for(int v=1;v<=50;v++){
        if(g[u][v]){
            g[u][v]--;
            g[v][u]--;

            dfs(v);
            printf("%d %d\n",v,u);//注意顺序是倒过来的

        }
    }
}
void inits(){
    memset(g,0,sizeof(g));
    memset(vis,0,sizeof(vis));
    memset(d,0,sizeof(d));
    ans.clear();
    flag=0;
}
int main(){
    int t;
    cin>>t;
    for(int o=1;o<=t;o++){
        scanf("%d",&n);
        inits();
        printf("Case #%d\n",o);
        for(int i=0;i<n;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            g[u][v]++;
            g[v][u]++;
            d[u]++;d[v]++;
        }
        for(int i=1;i<=50;i++){
            if(d[i]&1){
                flag=1;
                break;
            }
        }
        if(flag){
            printf("some beads may be lost\n\n");
        }
        else {
            for(int i=1;i<=50;i++){
                dfs(i);
            }   
            cout<<endl;
        }

    }
} 