By yusijia

Updated:

Contents
  1. 1. 题目大意：
  2. 2. 分析：

题目链接

参考

题目大意：

　　每个项链珠子有两个颜色(1<=i<=50)，现在要把他们串在一起，但每相邻两个珠子边上的颜色要相同，问能否实现。

分析：

　　把珠子两边的颜色看成一条边，要把所有的珠子串在一起，所以有回路，且最后回到起点，联想到欧拉回路问题。

  • 首先，图要连通，可以用并查集来实现判断
  • 然后，判断所有点的度数是否都为偶数
  • 满足前面两个，则输出路径
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

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 55;
int n, father[MAXN], mp[MAXN][MAXN], degree[MAXN], start;

void init()
{
    memset(mp, 0, sizeof(mp));
    memset(degree, 0, sizeof(degree));
    for(int i = 0; i < MAXN; i++){
        father[i] = i;
    }
}

int finds(int x)
{
    return father[x] == x ? father[x] : father[x] = finds(father[x]);
}

void union(int x, int y)
{
    int root_x = finds(x);
    int root_y = finds(y);
    father[root_x] = root_y;
}

bool isOk()
{
    int root = -1;
    for(int i = 0; i < MAXN; i++){
        if(degree[i] % 2 == 1)
            return false;
        if(degree[i]){//这里就利用到了初始化为0
            if(root == -1)
                root = finds(i);
            else{
                if(root != finds(i))//判断连通
                    return false;
            }
        }
    }
    return true;
}

void dfs(int cur)
{
    for(int i = 0; i < MAXN; i++){
        if(mp[cur][i]){
            mp[cur][i]--;//
            mp[i][cur]--;
            dfs(i);
            printf("%d %d\n", i, cur);//逆序输出
        }
    }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    int T, x, y, Case = 1;
    bool isFirst = true;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        init();
        for(int i = 0; i < n; i++){
            scanf("%d%d", &x, &y);
            start = x;
            mp[x][y]++;//把珠子看成无向边
            mp[y][x]++;
            degree[x]++;
            degree[y]++;
            union(x, y);
        }
        if(isFirst)
            isFirst = false;
        else
            printf("\n");
        printf("Case #%d\n" , Case++);
         if(!isOk())
             printf("some beads may be lost\n");
         else
             dfs(start);
    }
    return 0;
}
Contents
  1. 1. 题目大意：
  2. 2. 分析：