TIOJ 1084 . 一筆畫問題

dfs倒著吐回去


#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

int tab[500][500];
int vcnt[500];
int stk[1025], stkcnt;

void dfs(int a){
    bool flag = false;
    for(int lx = 0;lx < 500;lx++){
        if(tab[a][lx]){
            tab[a][lx]--;
            tab[lx][a]--;
            dfs(lx);
            flag = true;
            stk[stkcnt++] = a+1;
        }
    }
    if(!flag) stk[stkcnt++] = a+1;
    return;
}

int main(){
    int c;
    while(scanf("%d", &c)&&c){
        memset(tab, 0, sizeof(tab));
        memset(vcnt, 0, sizeof(vcnt));
        stkcnt = 0;

        while(c--){
            int a, b; scanf("%d %d", &a, &b); a--, b--;
            tab[a][b]++, tab[b][a]++;
            vcnt[a]++, vcnt[b]++;
        }
        bool check = true;
        for(int lx = 0;lx < 500 and check;lx++)
            check = not (vcnt[lx]&1);
       
        int sm = -1;
        if(check) while(!vcnt[++sm]);
        else  while(!(vcnt[++sm]&1));
        dfs(sm);

        for(int lx = stkcnt-1;lx>=0;lx--)
            if(lx == stkcnt-1 or stk[lx] != stk[lx+1])
                printf("%d\n", stk[lx]);
        puts("");
    }
    return 0;
}