欧拉路 / 一笔画

一笔画问题：给出 n 个点和 m 条边，边不可以重复走，问是否可以一笔走完所有边。能一笔画的图，要么存在欧拉回路（回到起点），要么存在欧拉通路（起终点不同）。

判定（连通前提下）：所有点度数均为偶数 → 存在欧拉回路（闭合，可任意点出发）；恰好 2 个奇度点 → 存在欧拉通路（从其中一个奇度点出发，在另一个奇度点结束）；其余（奇度点 >2 或为奇数个）→ 不能一笔画。代码中 res<=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++;
        }
        // 这里 sum 统计的是整图（含孤立点）的连通分量个数，sum!=1 即要求“整图连通”。
        // 若题目允许忽略孤立点（只要求有边的子图连通），应改为只对 deg[i]>0 的点计数：
        //   for(...){ if(deg[i]>0 && i==find(i)) sum++; if(deg[i]&1) res++; }  并把判定改成 sum>1（m=0 时 sum=0）。
        if(sum!=1)
            puts("不是");
        else
        {
            if(res<=2)
                puts("是");
            else
                puts("不是");
        }
    }
    return 0;
}

时间复杂度约 $O(n+m\cdot \alpha (n))$（并查集近似线性），空间 $O(n)$。

输出一笔画 / 欧拉路径：

若有 2 个奇度点则从奇度点开始 dfs 得到欧拉通路，若全为偶度点则从任意点开始 dfs 得到欧拉回路。在 dfs 的时候删去这个点连的所有边，最后利用 dfs 的特性，点的出栈顺序就是答案（即 Hierholzer 算法：每个点在其所有出边都走完后才出栈，故出栈逆序恰为一条欧拉路径）。下面代码默认从点 1 出发，存在奇度点时改从奇度点出发。

#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)
{
    // 边必须成对添加：add_edge(u,v) 紧跟 add_edge(v,u)，且 tot 从 0 开始，
    // 这样正反向边编号互为 i^1，dfs 中才能用 e[i^1].flag 同步标记反向边。
    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;
}

时间复杂度 $O(n+m)$（每条边只被访问一次），空间 $O(n+m)$。