P6066

Aryper · 2021-08-07 18:28:03 · 个人记录

[USACO05JAN]Watchcow S

POJ2230 。

然后这个就非常的巧妙。

我们知道 Hierholzer 算法中针对无向图要把无向图的无向边标记。

那么这个题要求正反各走一边，其实我们本来建的无向边就是两条有向边的拼凑，那干脆在标记的时候只标一个方向就解决了。

时间复杂度仍然是 O(nm) 。

然后数组好像要开大一点。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;

const ll N=1e5,M=5e5;

ll n,m,tot,top,t,u,v;

ll stk[M+5],ans[M+5];

ll ver[M*2+5],nxt[M*2+5],head[N+5];

bool vis[M*2+5];

void euler() {
    stk[++top]=1;
    while(top>0) {
        ll x=stk[top],i=head[x];
        while(vis[i]&&i) i=nxt[i];
        if(i) {
            stk[++top]=ver[i];
            vis[i]=1;
            head[x]=nxt[i];
        }
        else {
            top--;ans[++t]=x;
        }
    }
}

void add(ll u,ll v) {
    ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

int main() {

    n=read();m=read();
    for(ll i=1;i<=m;i++) {
        u=read();v=read();
        add(u,v);add(v,u);
    }
    euler();
    for(ll i=t;i;i--) printf("%lld\n",ans[i]);

    return 0;
}