By yusijia

Updated:

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

http://acm.hdu.edu.cn/showproblem.php?pid=1116

题目大意：

　　给n个单词，判断能否按要求串成一个长串， 要求，前一个单词的最后一个字母是后一个单词的第一个字母，有点类似成语接龙。

分析：

　　把每个单词的首位字母抽出来，看成一条边，由于这里的单词不像uva 10054里的珠子可以旋转着看，所以这里是有向图，然后求是否有欧拉回路或欧拉通路。

  • 首先，必须是单连通的路径，所以用并查集+set来判断连通分量的个数
  • 然后，如果是单连通的话，对于有向图来说，如果是欧拉回路，则所有点的入度等于出度。
    如果是欧拉通路，起点不等于终点，则只能有两个点的入度减出度的绝对值为1(起点的出度大，终点的入度大)，其余点入度等于出度。
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

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

const int MAXN = 30;//26个英文字母

int mp[MAXN][MAXN], father[MAXN], inDegree[MAXN], outDegree[MAXN], n;
bool vis[MAXN];

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

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

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

bool solve()
{
    set<int> s;
    int sum = 0;
    s.clear();
    for(int i = 0; i < MAXN; i++)if(vis[i]){
        s.insert(finds(i));
    }
    if(s.size() > 1)
        return false;
    for(int i = 0; i < MAXN; i++){
        if(abs(inDegree[i] - outDegree[i]) > 1)//出入度数差只能为1或0
            return false;
        //这里只需要处理出入度差1的情况，但要判断是否有出入度差大于1的情况
        /*if(inDegree[i] == outDegree[i]) continue;*/ //一开始没判断出入度大于1的情况，就WA了
        if(abs(inDegree[i] - outDegree[i]) == 1)//
            sum++;
    }
    return (sum == 2 || sum == 0);
}

int main()
{
    //freopen("input.txt", "r", stdin);
    char str[1010];
    int T, x, y;
    scanf("%d", &T);
    while(T--){
        init();
        scanf("%d", &n);
        for(int i = 0; i < n; i++){
            scanf("%s", str);
            x = str[0] - 'a';
            y = str[strlen(str) - 1] - 'a';
            inDegree[y]++, outDegree[x]++;
            mp[x][y]++;
            vis[x] = vis[y] = true;
            unions(x, y);
        }
        if(n == 1 || solve())
            printf("Ordering is possible.\n");
        else
            printf("The door cannot be opened.\n");
    }
    return 0;
}
Contents
  1. 1. 题目大意：
  2. 2. 分析：