Problem Solving►UVa

UVa 10054 - The Necklace

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址

給定各個珠子的顏色，每個珠子要相連，它們連接地方的顏色要相同。
有多種答案表示，任一種都可。

Solution

把顏色當作點，珠子當作邊，來做歐拉迴路。

關於歐拉迴路的定義和做法可參考:
https://zh.wikipedia.org/wiki/一笔画问题
演算法筆記

主要就是利用歐拉迴路中，隨便走一圈直到不能走，會是個小的歐拉迴路，也就是到達剛剛的起點。以此為基礎遞迴將每個小歐拉迴路走完。(D&C)
還有利用每個點的 degree 來判斷這張圖是否是歐拉迴路。(每個頂點的 degree 都是偶數)

處理顏色時，可額外用陣列依序對應其顏色，加速查詢。

Code

UVa 10054
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<cstdio>
#include<vector>
#include<deque>
#define N 51
using namespace std;

vector<int> adjList[N];
deque<int>ans;
int now[N];//[x],x 的邊已進行到哪條了
int edgeNum[N][N];//兩點之間的邊數。自環會重複算
void findEuler(int x);
int main()
{
    int Case;
    scanf("%d", &Case);
    for (int c = 1; c <= Case; c++)
    {
        if (c != 1)
            putchar('\n');
        //---init---
        int n, i, c1, c2, E = 0, count = 0;
        int deg[N] = {}, map[N] = {}, reMap[N] = {};
        for (i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                edgeNum[i][j] = 0;
        for (i = 0; i < N; i++)
            now[i] = 0;
        for (i = 0; i < N; i++)
            adjList[i].clear();
        ans.clear();
        //---

        scanf("%d", &n);
        for (i = 0; i < n; i++)
        {
            scanf("%d%d", &c1, &c2);

            if (!map[c1])
            {
                map[c1] = ++count;
                reMap[map[c1]] = c1;
            }
            if (!map[c2])
            {
                map[c2] = ++count;
                reMap[map[c2]] = c2;
            }

            c1 = map[c1];
            c2 = map[c2];

            //建邊
            adjList[c1].push_back(c2);
            adjList[c2].push_back(c1);

            //計算兩點之間的邊數
            edgeNum[c1][c2]++;
            edgeNum[c2][c1]++;

            deg[c1]++;
            deg[c2]++;

            E++;
        }

        //判斷邊的 degree 是否為偶數
        for (i = 1; i <= count; i++)
            if (deg[i] & 1)
                break;

        printf("Case #%d\n", c);
        if (i <= count)
            puts("some beads may be lost");
        else
        {
            findEuler(count);//從最後一點開始
            int size = ans.size();
            if (size / 2 != E)//圖不連通
                puts("some beads may be lost");
            else
                for (i = 0; i < size; i += 2)
                    printf("%d %d\n", reMap[ans[i]], reMap[ans[i + 1]]);
        }
    }

    return 0;
}
void findEuler(int x)
{
    int size = adjList[x].size();
    for (int v = now[x]; v < size; v++)
    {
        int next = adjList[x][v];
        if (edgeNum[x][next])
        {
            edgeNum[x][next]--;
            edgeNum[next][x]--;

            findEuler(next);

            //x -> next
            ans.push_front(next);
            ans.push_front(x);
        }
        else//x 連到 y 的所有邊都走過了，待會再遇到 x 就可從下一個點開始走了。
            now[x]++;
    }
}