欧拉回路

欧拉回路也就是一笔画问题，给出n个点和m条边，边不可以重复走，问是否可以走完。

欧拉回路的判定是: 如果一个连通图的奇数度的点的个数不超过2个,如果成立就是欧拉回路，否则就不是

判断是否是欧拉回路:先用并查集判断图是否连通，然后在判断点的度数

const int N=1e5+10;
int pre[N],deg[N];
int n,m;
void init()
{
    for(int i=1; i<=n; i++)
        pre[i]=i;
    mem(deg,0);
}
int find(int x)
{
    return x==pre[x]?x:pre[x]=find(pre[x]);
}
void mix(int x,int y)
{
    int fx=find(x),fy=find(y);
    if(fx!=fy)
        pre[fy]=fx;
}
int main()
{
    int t,u,v;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        init();
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d",&u,&v);
            mix(u,v);
            deg[u]++,deg[v]++;
        }
        int sum=0,res=0;
        for(int i=1; i<=n; i++)
        {
            if(i==find(i))
                sum++;
            if(deg[i]&1)
                res++;
        }
        if(sum!=1)
            puts("不是");
        else
        {
            if(res<=2)
                puts("是");
            else
                puts("不是");
        }
    }
    return 0;
}

输出欧拉回路路径:

从一个奇数度的节点开始进行dfs，在dfs的时候删去这个点连得所有边，最后利用dfs的特性，点的出栈顺序就是答案

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
const int N=10000+50;
int in[N];
int first[N],tot,len=0;
stack<int>s;
struct node
{
    int v,next,flag;
} e[N];
void add_edge(int u,int v)
{
    e[tot].v=v;
    e[tot].flag=0;
    e[tot].next=first[u];
    first[u]=tot++;
}
void init()
{
    mem(first,-1);
    mem(in,0);
    tot=0;
}
void dfs(int u)
{
    for(int i=first[u]; ~i; i=e[i].next)
    {
        int v=e[i].v;
        if(!e[i].flag)
        {
            e[i].flag=1;
            e[i^1].flag=1;
            dfs(v);
        }
    }
    s.push(u);
}
int main()
{
    int n,m,u,v;
    scanf("%d%d",&n,&m);
    init();
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&u,&v);
        add_edge(u,v);
        add_edge(v,u);
        in[u]++,in[v]++;
    }
    u=1;
    for(int i=2; i<=n; i++)
        if(in[i]&1)
        {
            u=i;
            break;
        }
    dfs(u);
    while(s.size()>1)
    {
        printf("%d ",s.top());
        s.pop();
    }
    printf("%d\n",s.top());
    return 0;
}