[HOJ] 148 - 海綿寶寶之泡芙阿姨駕訓班(尤拉路徑)

#include<stdio.h>
#include<vector>
using namespace std;
struct{
    int p,vis;
}edge[2000005]={0};
vector<int> s[500005],ans;
int top=0,add[500005]={0};
void dfs(int k){
    int i,r;
    for(i=0;i<s[k].size();i++){
        r=s[k][i];
        if(edge[r].vis==0){
            edge[r].vis=edge[r^1].vis=1;
            dfs(edge[r].p);
            ans.push_back(r);
        }
    }
}
int main(){
    int n,m,i,x,y;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++){
        scanf("%d%d",&x,&y);
        add[x]++,add[y]++;
        s[x].push_back(top);
        s[y].push_back(top+1);
        edge[top++].p=y,edge[top++].p=x;
    }
    for(i=1;i<=n;i++)
        if(add[i]%2)
            x=i;
    dfs(x);
    for(i=0;i<ans.size();i++){
        x=ans[i];
        printf("%d %d\n",edge[x].p,edge[x^1].p);
    }
}