Условие: Всем известны правила игры "в города": первый игрок называет произвольный город, следующий - город, название которого начинается на ту же букву, на которую заканчивается название предыдущего города, и т.д. Аналогичным образом можно играть не в названия городов, а, например, в названия животных. Задан список допустимых для описанной игры слов, слова в нём могут повторяться. Напишите программу, определяющую, в каком порядке в процессе игры должны быть названы слова из списка, чтобы каждое слово было использовано ровно столько раз, сколько оно в нём встречается.
Технические условия: Во входном файле на первой строке записано число N - количество слов в списке (1<=N<=1000), а в последующих N строках - сами слова. Каждое из них является последовательностью не более, чем 10 строчных английских букв. Выведите в выходной файл слова в исходном порядке, либо сообщение "NO", если такого порядка не существует. Каждое слово должно быть выведено в отдельную строку выходного файла.
Примеры входных и выходных файлов: Input.txt 4 b ab bb bb Output.txt ab bb bb b
Решение: by Алексей Ильичёв <alex_z77@mail.ru>
---------- cut ---------- Если построить граф, в котором буквы английского алфавита являются вершинами, а данные нам слова - рёбрами, то задача сведётся к построению Эйлерова пути в ориентированном графе.
Как изменится условие существования Эйлерова пути для ориентированного графа? Нетрудно понять, что для существования в ориентированном графе Эйлерова пути необходимо и достаточно, чтобы для каждой вершины кол-во входящих рёбер равнялось кол-ву выходящих, или для одной вершины кол-во входящих рёбер было больше на 1, а для другой кол-во выходящих было больше на 1. При этом каждое ребро должно быть достижимым, то есть нет вершины, к которой подходит ребро и к которой нет пути из стартовой вершины.
Собственно алгоритм построения пути тот же самый, что и для неориентированного графа, за стартовую вершину принимается вершина, для которой кол-во выходящих рёбер на 1 больше.
PS. Если нужна дополнительная информация, такая например как теорема Эйлера с доказательством, или алгоритм построения Эйлерова пути - пишите. ---------- cut ----------
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.
