UVa10054 - The Necklace(Euler Circuit 歐拉迴路)

題目大意

有一個用各種顏色珠珠串成一起的項鍊，其中規則是相同顏色連在一起，有一天這個項鍊珠子跟其他的珠子混在一起了，希望你可以在裡面找到能夠符合先前規則的珠子，並組成項鍊

註：輸出時並須按照順序輸出。
題目連結

重點觀念

• Euler Circuit 歐拉迴路

分析

• 實作歐拉無向圖迴路

題目程式碼

有一些程式碼註解在 Euler Circuit 歐拉迴路 by 大衛的筆記請供參考。

詳解的部分請詳看，Euler Circuit 歐拉迴路 by 大衛的筆記 中的程式碼說明

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
using namespace std;
const int MAXN = 1020;
int t, n, kase = 0, a, b;
vector<int> edge[MAXN];
int g[MAXN][MAXN];
int degree[MAXN];
vector<pair<int,int> > record;


void euler(int root){

    for(int it: edge[root]){
        if(!g[root][it]) continue;
        g[root][it]--;
        g[it][root]--;
        euler(it);
        cout << "root it " << root << " " << it << "\n";
        record.push_back({root, it}); //記得逆序，因為遞迴，會將後面的 dfs 先 print 出來
    }
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // LOCAL
    cin >> t;
    while(t--){
        for(int i = 0; i < 55; i++) edge[i].clear();
        memset(degree, 0, sizeof(degree));
        memset(g, 0, sizeof(g));
        if(kase >= 1) printf("\n");

        cin >> n;
        for(int i = 0; i < n; i++){
            cin >> a >> b;
            edge[a].push_back(b);
            edge[b].push_back(a);
            g[a][b]++;
            g[b][a]++;
            degree[a]++;
            degree[b]++;
        }

        int flag = 0;
        for(int i = 0; i < 55; i++){
            if(degree[i] % 2 != 0){
                flag = 1;
                break;
            }
        }
        cout << "Case #" << ++kase << '\n';
        if(flag) cout << "some beads may be lost\n";
        else{
            record.clear();
            euler(a);
            for(auto it: record) cout << it.first << " " << it.second << '\n';
        }
        //cout << "\n";
    }
    return 0;
}

參考連結

UVA 10054 - The Necklace by SCJ