百搭背心★瘋搶↘120女大生禁不起誘惑!按了..正妹的東京自助旅行睽違25天終開會 立院...
2012-06-06 11:35:51 人氣(362) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][EularCircuit] 10054 - The Necklace

0
收藏
0
推薦


  Problem D: The Necklace 

My little sister had a beautiful necklace made of colorful beads. Two successive beads in the necklace shared a common color at their meeting point. The figure below shows a segment of the necklace:

But, alas! One day, the necklace was torn and the beads were all scattered over the floor. My sister did her best to recollect all the beads from the floor, but she is not sure whether she was able to collect all of them. Now, she has come to me for help. She wants to know whether it is possible to make a necklace using all the beads she has in the same way her original necklace was made and if so in which order the bids must be put.

Please help me write a program to solve the problem.

Input 

The input contains T test cases. The first line of the input contains the integer T.

The first line of each test case contains an integer N ( $5 le
N le 1000$) giving the number of beads my sister was able to collect. Each of the next N lines contains two integers describing the colors of a bead. Colors are represented by integers ranging from 1 to 50.

Output 

For each test case in the input first output the test case number as shown in the sample output. Then if you apprehend that some beads may be lost just print the sentence ``some beads may be lost" on a line by itself. Otherwise, print N lines with a single bead description on each line. Each bead description consists of two integers giving the colors of its two ends. For $1 le i le N ­ 1$, the second integer on line i must be the same as the first integer on line i + 1. Additionally, the second integer on line N must be equal to the first integer on line 1. Since there are many solutions, any one of them is acceptable.

Print a blank line between two successive test cases.

Sample Input 

2
5
1 2
2 3
3 4
4 5
5 6
5
2 1
2 2
3 4
3 1
2 4

Sample Output 

Case #1
some beads may be lost
 
Case #2
2 1
1 3
3 4
4 2
2 2

參考演算法筆記找出其中一條尤拉迴路,
由於尤拉迴路已經確定了, 因此可以明確知道在 dfs 的過程中不會有例外產生,
不仿想一想, 其實也不難想

#include <stdio.h>
#include <string.h>

int map[51][51], deg[51];
int p[51], r[51];
void init() {
    int i;
    for(i = 0; i <= 50; i++) {
        p[i] = i, r[i] = 1;
    }
}
int find(int x) {
    return x == p[x] ? x : (p[x]=find(p[x]));
}
int joint(int x, int y) {
    x = find(x), y = find(y);
    if(x != y) {
        if(r[x] > r[y])
            r[x] += r[y], p[y] = x;
        else
            r[y] += r[x], p[x] = y;
        return 1;
    }
    return 0;
}
void dfs(int node) {
    int i;
    for(i = 1; i <= 50; i++) {
        if(map[node][i]) {
            map[node][i]--;
            map[i][node]--;
            dfs(i);
            printf("%d %d\n", i, node);
        }
    }
}
int main() {
    int t, test = 0, n, x, y, i;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        memset(map, 0, sizeof(map));
        memset(deg, 0, sizeof(deg));
        init();
        while(n--) {
            scanf("%d %d", &x, &y);
            map[x][y]++;
            map[y][x]++;
            deg[x]++, deg[y]++;
            joint(x, y);
        }
        printf("Case #%d\n", ++test);
        int st, flag = 0;
        for(i = 1; i <= 50; i++) {
            if(deg[i]) {
                st = i;
                if(deg[i]&1)
                    flag = 1;
            }
        }
        for(i = 1; i <= 50; i++) {
            if(deg[i]) {
                if(find(st) != find(i))
                    flag = 1;
            }
        }
        if(flag)
            puts("some beads may be lost");
        else
            dfs(st);
        if(t)
            puts("");
    }
    return 0;
}

10054The NecklaceEularCircuit
台長:Morris
人氣(362) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][dfs] 165 - Stamps
此分類上一篇:[UVA][sort] 612 - DNA Sorting

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文