TIOJ 1084 一筆畫問題

poao899    184K    15MS    G++     1.43K     2009-11-03 22:40:43                              .


當我在co時我到底有沒有計畫我要co什麼

蚯蚓：你這樣可能寫不了大程式


另外不從1開始好糟糕Q

最近開始轉USACO  可能這裡放的題目會少一點XD

//*******************************

#include<stdio.h>
#include<algo.h>
struct edge{
    int j;
    bool use;
    edge *next,*topair;
    bool operator<(const edge &b)const{
        return j<b.j;
    }
}E[3000],*V[1000],tmp[1000];
int deg[1000];
int m;
int trace[3000];
int top,cnt;
void set(int i,int j){
    E[cnt].topair=&E[cnt+1];
    E[cnt].use=1;
    E[cnt].j=j;
    edge *p=V[i];
    V[i]=E+cnt;
    E[cnt].next=p;
    cnt++;
   
    E[cnt].topair=&E[cnt-1];
    E[cnt].use=1;
    E[cnt].j=i;
    p=V[j];
    V[j]=E+cnt;
    E[cnt].next=p;
    cnt++;
    deg[i]++;
    deg[j]++;
}
void dfs(int node){
    while(V[node]!=NULL){
        if(V[node]->use){
            V[node]->use = V[node]->topair->use = 0;
            int x=V[node]->j;
            V[node]=V[node]->next;
            dfs(x);
        }
        else
            V[node] = V[node]->next;
    }
    trace[top++]=node;
    return;
}
main(){
    while(scanf("%d",&m),m){
        top=0;
        cnt=0;
        for(int i=0;i<1000;i++){
            V[i]=NULL;
            deg[i]=0;
        }
        for(int i=0;i<m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            set(a,b);
        }
        int n;
        for(n=1;n<1000;n++){
            edge *p;
            int i;
            for(i=0,p=V[n];p!=NULL;p=p->next)
                tmp[i++]=*p;
            sort(tmp,tmp+i);
            for(i=0,p=V[n];p!=NULL;p=p->next){
                p->j=tmp[i].j;
                tmp[i].topair->topair=p;
                p->topair=tmp[i].topair;
                i++;
            }
        }
        int start=9999;
        for(int i=1;i<n;i++){
            if(deg[i]>0){
                start<?=i;
            }
            if(deg[i]%2){
                start=i;
                break;
            }
        }
        dfs(start);
        while(top)
            printf("%d\n",trace[--top]);
        puts("");
    }
}