跳转至

欧拉路

有向图欧拉路

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
namespace EulerRoad
{
    struct edge{int nex,to;}e[MAX];
    int head[MAX],cnt;
    int in[MAX],out[MAX],ans[MAX],con;
    int stk[MAX],top,fl1,fl2,fl3;

    inline bool work()
    {
        fl1=1,s=1;
        for(int i=1;i<=n;++i)
        {
            if(in[i]!=out[i]) fl1=0;
            if(out[i]-in[i]==1) s=i,++fl2;
            if(in[i]-out[i]==1) ++fl3;
        }
        if(!(fl1||(fl2==1&&fl3==1))) return 0;
        stk[++top]=s;
        while(top)
        {
            int now=stk[top],i=head[now];
            if(i) stk[++top]=e[i].to,head[now]=e[i].nex;
            else --top,ans[++con]=now;
        }
        return 1;
    }
}