poj2230 Watchcow

扔一个欧拉路板子

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;

struct node
{
    int x,y,next;
}a[110000];int len,last[11000];
void ins(int x,int y)
{
    len++;
    a[len].x=x;a[len].y=y;
    a[len].next=last[x];last[x]=len;
}

int top,sta[110000],cur[11000]; bool v[110000];
int aslen,as[110000];
void euler()
{
    top=0;sta[++top]=1;
    memset(v,false,sizeof(v));
    memcpy(cur,last,sizeof(cur));
    while(top!=0)
    {
        int x=sta[top],k;
        for(k=cur[x];k&&v[k];k=a[k].next);
        if(k)
        {
            sta[++top]=a[k].y;
            v[k]=true;
            cur[x]=a[k].next;
        }
        else top--,as[++aslen]=x;
    }
}
int main()
{
    int n,m,x,y;
    scanf("%d%d",&n,&m);
    len=0;memset(last,0,sizeof(last));
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        ins(x,y);ins(y,x);
    }
    euler();
    for(int i=aslen;i>=1;i--)printf("%d
",as[i]);
    return 0;
}