Solution UVA: 10054 - The Necklace

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10054 - The Necklace	Accepted	C++11	0.350	0.050	2271	2 hours ago

Suggest:

- If you have not study Euler but you want to solve this problem, you should run recursion on paper. That's the fastest way to understand the problem (me too)

#include<bits/stdc++.h>

#define X first

#define Y second

using namespace std;

const int N= 1011;

int a[N][N];

int n;  

void euler(int u){

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

        if (a[u][v] > 0){

            a[u][v]--, a[v][u]--;

            euler(v);

            cout<<v<<" "<<u<<"\n";

        }

}

int main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

   

    int t;  cin >> t;

    int kase= 0;

   

    while(t--){ if (kase++) cout<<"\n";

        cin >> n;

        unordered_map<int, int> cnt;

        for(int i=1; i<=50; i++) for(int j=1; j<=50; j++) a[i][j]= 0;

       

        int u, v;  

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

            cin >> u >> v;  

            a[u][v]++, a[v][u]++;

            cnt[u]++, cnt[v]++;

        }

         

        cout<<"Case #"<<kase<<"\n";

        bool lost= false;

        for(auto v : cnt)

            if (v.Y%2) lost= true;

        if (lost) cout<<"some beads may be lost\n";

        else{

            euler(u);

        }

               

    }

}