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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
| program game;
var
n, i, j : integer;
wrd : array[1..1000] of string[10]; {Тут храним слова}
rin, rout, {Кол-во входящих и выходящих рёбер}
hash : array[1..26] of integer; {указатель на элемент массива рёбер,
с которого начинаются рёбра, выходящие из данной вершины}
s, f : array[0..1000] of integer; {список рёбер - номера начальных и
конечных вершин}
sv, fv, {начальная и конечная вершины}
v : integer;
avail : array[1..26] of boolean; {существует ли путь из стартовой вершины
в данную}
way, ret : array[0..1000] of integer; {очередь рёбер}
deleted : array[1..1000] of boolean; {отмечаем уже использованные слова}
found : boolean;
procedure swap(i, j : integer);
var
st : string[10];
w : integer;
begin
w := s[i];
s[i] := s[j];
s[j] := w;
w := f[i];
f[i] := f[j];
f[j] := w;
st := wrd[i];
wrd[i] := wrd[j];
wrd[j] := st;
end;
procedure sort(l, r : integer);
var
x, i, j : integer;
begin
i := l;
j := r;
x := s[(l + r) div 2];
repeat
while s[i] < x do inc(i);
while s[j] > x do dec(j);
if i <= j then begin
swap(i, j);
inc(i);
dec(j);
end;
until i > j;
if i < r then sort(i, r);
if j > l then sort(l, j);
end;
procedure check(v : integer);
var
i : integer;
begin
avail[v] := true;
i := hash[v];
while (s[i] = v) do begin
if not avail[f[i]] then check(f[i]);
inc(i);
end;
end;
procedure movefrom(v : integer);
var
i : integer;
found : boolean;
begin
ret[0] := 0;
repeat
found := false;
i := hash[v];
while (s[i] = v) and (deleted[i]) do inc(i);
if s[i] = v then begin
found := true;
deleted[i] := true;
inc(ret[0]);
ret[ret[0]] := i;
v := f[i];
end;
until not found;
end;
begin
assign(input,'input.txt');
reset(input);
readln(n);
for i := 1 to n do begin
readln(wrd[i]);
s[i] := ord(wrd[i, 1]) - ord('a') + 1;
f[i] := ord(wrd[i, length(wrd[i])]) - ord('a') + 1;
inc(rout[s[i]]);
inc(rin[f[i]]);
end; {читаем данные, считаем кол-во подходящих рёбер для каждой вершины}
close(input);
sort(1, n); {сортируем рёбра по начальной вершине}
for i := 1 to 26 do
if (rout[i] - rin[i] = 1) and (sv = 0) then sv := i
else if (rin[i] - rout[i] = 1) and (fv = 0) then fv := i
else if (rout[i] <> rin[i]) then begin
assign(output, 'output.txt');
rewrite(output);
writeln('NO');
close(output);
halt;
end; {Проверяем первое условие существования пути, записываем
стартовую и конечную вершины}
for i := 1 to n do if hash[s[i]] = 0 then hash[s[i]] := i; {формируем
массив указателей на элементы списка рёбер для каждой вершины}
if sv = 0 then for i := 1 to 26 do if rout[i] > 0 then sv := i; {если
стартовую вершину найти не удалось, берём произвольную}
check(sv); {обходом в глубину закрашиваем компоненту связности,
к которой относится первая вершина}
for i := 1 to 26 do if (not avail[i]) and (rin[i] > 0) then begin
assign(output, 'output.txt');
rewrite(output);
writeln('NO');
close(output);
halt;
end; {если не все рёбра достижимы, значит пути нет}
v := sv;
repeat
found := false;
i := hash[v];
while (s[i] = v) and deleted[i] do inc(i);
if s[i] = v then begin
found := true;
inc(way[0]);
way[way[0]] := i;
deleted[i] := true;
v := f[i];
end;
until not found; {идём от стартовой вершины, пока не упрёмся в конечную}
v := sv;
i := 0;
while i <= way[0] do begin
if rout[v] > 0 then begin
movefrom(v);
for j := way[0] downto i + 1 do way[j + ret[0]] := way[j];
inc(way[0], ret[0]);
move(ret[1], way[i+1], ret[0] shl 1);
end;
inc(i);
v := f[way[i]];
end; {добавляем к нашему пути все возможные циклы}
assign(output, 'output.txt');
rewrite(output);
for i := 1 to way[0] do writeln(wrd[way[i]]); {выводим ответ}
close(output);
end. |
(
Сообщение от Argento
