The Necklace

題目鏈接

題意：
給很多由兩個顏色組成的珠子，看是否能連成一串，相鄰珠子相鄰部分顏色相同分析：
裸地歐拉路判斷+路徑輸出，不過這個題輸出要求是以點為單位輸出，所以不用記錄邊的序號之類的注意：
數據中會有重邊，所以搜索路徑的時候要記錄一下每條邊的數量，每走過一次值減一，所以不能再使用set

const int MAXV = 60;
const int MAXE = 1020;

struct Undirect_Euler
{
    int father[MAXV], num[MAXV];
    vector vt[MAXV];
    stack sk;
    int edge[MAXV][MAXV];
    set st;

    void init()
    {
        CLR(edge, 0);
        while (!sk.empty())
            sk.pop();
        REP(i, MAXV)
        {
            num[i] = 1;
            father[i] = i;
            vt[i].clear();
        }
        st.clear();
    }
    int find(int n)
    {
        return father[n] == n ? n : father[n] = find(father[n]);
    }
    bool isOne(int ind)
    {
        return num[find(ind)] == st.size();
    }
    void merge(int a, int b)
    {
        st.insert(a);
        st.insert(b);
        vt[a].push_back(b);
        vt[b].push_back(a);
        edge[a][b]++;
        edge[b][a]++;
        int fa = find(a), fb = find(b);
        if (fa != fb)
        {
            num[fa] += num[fb];
            father[fb] = fa;
        }
    }
    // n:判斷前n個點是否是一個集合(並查集使用)
    //是返回true,而且如果是歐拉回路circle = 0,如果是歐拉路circle > 0
    //不是返回false
    bool isEulerRoad(int someone, int& tot, int* ind)
    {
        if (!isOne(someone))
            return false;
        tot = 0;
        REP(i, MAXV)
        {
            if (vt[i].size() % 2 != 0)
            {
                ind[tot++] = i;
                if (tot > 2) return false;
            }
        }
        return tot == 0 || tot == 2;
    }
    //搜索路徑,結果保留在sk中
    void solve(int n)
    {
        REP(i, vt[n].size())
        {
            int next = vt[n][i];
            if (edge[n][next] > 0)
            {
                edge[n][next]--;
                edge[next][n]--;
                solve(next);
            }
        }
        sk.push(n);
    }
    //輸出路徑,自己寫格式
    void display()
    {
        int t = 0;
        vector vt;
        while (!sk.empty())
        {
            vt.push_back(sk.top());
            sk.pop();
        }
        int len = vt.size();
        REP(i, len - 1)
        {
            printf("%d %d\n", vt[i], vt[i + 1]);
        }
    }
} graph;


int main()
{
//    freopen("in.txt", "r", stdin);
    int K, n, a, b;
    RI(K);
    FE(kase, 1, K)
    {
        graph.init();
        RI(n);
        REP(i, n)
        {
            RII(a, b);
            graph.merge(a, b);
        }
        if (kase != 1)
            puts("");
        printf("Case #%d\n", kase);
        int tot = 0, ind[10];
        if (graph.isEulerRoad(a, tot, ind) && tot == 0)
        {
            graph.solve(a);
            graph.display();
        }
        else
        {
            puts("some beads may be lost");
        }
    }
    return 0;
}