UVA 10054 - The Necklace

UVA 10054 - The Necklace

題目概述:

給一個無向圖，輸出尤拉迴路(Eulerian Circuit)。

思路:

以下實作方式直接以遞迴方式，不利用stack將路徑存起來。

關於證明或細節可以參考 https://www.youtube.com/watch?v=0sRR-bgXV-I

個人在寫的時候WA了幾次，原因在於我DFS的起始點都假定為1，但其實不一定每組測資都保證有1，所以需要隨便丟一個出現的點去DFS，可能要注意一下。

AC code:

//By SCJ

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

struct P{

   int x,y;

};

vector<P> G[52];//x->node y->edge

P es[1002];

bool used[1002];

void dfs(int u)

{

   for(P e:G[u])

   {

       if(used[e.y]) continue;

       used[e.y]=1;

       dfs(e.x);

       cout<<e.x<<' '<<u<<endl;

   }

}

int n,degree[52];

void init()

{

   for(int i=0;i<52;++i) G[i].clear();

   memset(degree,0,sizeof(degree));

   cin>>n;

   for(int i=1;i<=n;++i)

   {

       int a,b;

       cin>>a>>b;

       es[i]={a,b};

       G[a].push_back({b,i});

       G[b].push_back({a,i});

       degree[a]++;degree[b]++;

   }

}

void solve()

{

   for(int i=1;i<=50;++i)

   {

       if(degree[i]&1)

       {

           cout<<"some beads may be lost"<<endl;

           return ;

       }

   }

   memset(used,0,sizeof(used));

   dfs(es[1].x);

}

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   int T;cin>>T;

   for(int no=1;no<=T;++no)

   {

       if(no!=1) cout<<endl;

       cout<<"Case #"<<no<<endl;

       init();

       solve();

   }

}