POJ 1386 - Play on Words

http://poj.org/problem?id=1386

概要

小文字のアルファベットからなる単語が書かれた \(N\) 枚のプレートがある。 これを、どのプレートの単語もその前のプレートの単語の最後の文字から始まるように一列に並べることができるかどうか答える。

制約

• \(1 \le N \le 10 ^ 5\)

解法

どの単語も最初と最後の2文字にだけ注目すれば十分。 あとは

• 各文字について、開始位置にきている単語数と終端位置にきている単語数の差が高々1しかない
• 出現する文字が連結である

ことをチェックすればいい。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <vector>
 4 using namespace std;
 5 
 6 struct DisjointSet/*{{{*/
 7 {
 8   vector<int> parent;
 9 
10   int root(int x)
11   {
12     if (parent[x] < 0) {
13       return x;
14     } else {
15       parent[x] = root(parent[x]);
16       return parent[x];
17     }
18   }
19 
20   explicit DisjointSet(int n) : parent(n, -1) {}
21 
22   bool unite(int x, int y)
23   {
24     const int a = root(x);
25     const int b = root(y);
26     if (a != b) {
27       if (parent[a] < parent[b]) {
28         parent[a] += parent[b];
29         parent[b] = a;
30       } else {
31         parent[b] += parent[a];
32         parent[a] = b;
33       }
34       return true;
35     } else {
36       return false;
37     }
38   }
39 
40   bool find(int x, int y) { return root(x) == root(y); }
41   int size(int x) { return -parent[root(x)]; }
42 };/*}}}*/
43 
44 int main()
45 {
46   int T;
47   scanf("%d", &T);
48   while (T-- > 0) {
49     int N;
50     scanf("%d", &N);
51     vector<int> beg(26, 0), end(26, 0);
52     DisjointSet s(26);
53     int c;
54     for (int i = 0; i < N; i++) {
55       char buf[1001];
56       scanf("%s", buf);
57       const int b = buf[0]-'a', e = buf[strlen(buf)-1]-'a';
58       ++beg[b];
59       ++end[e];
60       s.unite(b, e);
61       c = b;
62     }
63 
64     bool connected = true;
65     for (int i = 0; i < 26; i++) {
66       if ((beg[i] || end[i]) && !s.find(c, i)) {
67         connected = false;
68         break;
69       }
70     }
71     if (!connected) {
72       puts("The door cannot be opened.");
73       continue;
74     }
75 
76     int b = 0, e = 0;
77     for (int i = 0; i < 26; i++) {
78       if (beg[i] > end[i]) {
79         b += beg[i] - end[i];
80       } else if (beg[i] < end[i]) {
81         e += end[i] - beg[i];
82       }
83     }
84     if (b < 2 && e < 2) {
85       puts("Ordering is possible.");
86     } else {
87       puts("The door cannot be opened.");
88     }
89   }
90   return 0;
91 }