Условие задачи
Вводится последовательность, состоящая из [latex]N[/latex] пар символов [latex](a_i, b_i)[/latex]. Каждая пара определяет порядок предшествования символов, например, пара [latex](b, c)[/latex] означает, что символ [latex]b[/latex] предшествует символу [latex]c[/latex]. Из порядка [latex](b, c)[/latex] и [latex](c, a)[/latex] следует порядок [latex](b, a)[/latex]. Необходимо определить, является ли введенная последовательность:
а) полной, т.е. все использованные для формирования пар символы (выбросив повторяющиеся) можно выстроить в цепочку [latex]A_{1},A_{2}, \cdots ,A_{s}[/latex] в порядке предшествования;
б) противоречивой, т.е. для некоторых символов [latex]x,y[/latex] можно получить одновременно порядок как [latex](x, y)[/latex] так и [latex](y, x)[/latex];
Тесты
| Входные данные | Результат |
| 4 a b b c c d b d |
полный порядок |
| 3 2 a 8 c c b |
порядок неполный |
| 3 2 a 8 c a 8 |
полный порядок |
| 4 2 a 8 c c 2 a c |
Порядок противоречив |
| 10 a 5 5 4 b 3 3 4 5 3 b 5 a b 4 * * 0 4 0 |
полный порядок |
Код программы
|
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 |
#include <iostream> #include <algorithm> //для использования функции sort using namespace std; int main() { const int lch = 256; int n; cin>>n; char **p = new char* [n]; //Создаем массив p, где будем хранить пары символов. for (int i = 0; i < n; i++) { p[i] = new char [2]; } for (int i = 0; i < n; i++) { cin >> p[i][1]>>p[i][2]; } int chars[lch]; for (int i = 0; i<lch; i++) { chars[i] = -1; } int K = 0; for (int i = 0; i<n; i++) { if (chars [ p[i][1]] == -1) K++; if (chars [ p[i][2]] == -1) K++; chars [ p[i][1]] = 0; chars [ p[i][2]] = 0; } bool change; char x, y; int M; for (int i = 0; i < n; i++) { change = false; for (int j = 0; j < n; j++) { x = p[j][1]; y = p[j][2]; M = max(chars[x] + 1, chars [y]); if (M > (K-1)) { cout<<"Порядок противоречив"; return 0; } if (chars[y] != M) { change = true; } chars[y] = M; } if (!change) { sort(chars, chars+lch); int previous = K; int i = lch-1; while (chars [i] > -1) { if (chars[i] == previous - 1) { previous--; } else { cout<<"порядок неполный"; return 0; } i--; } cout<<"полный порядок"; return 0; } } return 0; } |
Решение
Общая идея решения
Эта часть решения взята отсюда.
Пусть при записи этих [latex]N[/latex] пар встретилось всего [latex]K[/latex] различных символов, которые образуют множество [latex]X[/latex].
Идея решения задачи состоит в последовательном присвоении каждому символу [latex]s[/latex] из [latex]X[/latex] номера, который определяет количество [latex]P(s)[/latex] элементов, предшествующих ему, с учетом свойства транзитивности (из [latex](c, b)[/latex] и [latex](b, a)[/latex] следует [latex](c, a)[/latex]). Это осуществляется следующим образом:
Первоначально предполагается, что каждому символу не предшествует ни один символ, т.е. [latex]P(s)=0[/latex] для любого [latex]s[/latex].
При просмотре очередной пары [latex](x, y)[/latex] символу y присваивается большее из значений [latex]P(x)+1, P(y)[/latex].
Очевидно, что при первом просмотре всех пар из входной последовательности определятся все упорядоченные цепочки длины 2, т.е. состоящие из 2 элементов. Поэтому номера некоторых элементов будут как минимум 1. При каждом из следующих просмотров входной строки возможно несколько вариантов.
- Не произошло изменения ни одного из номеров символов. Если при этом номера символов различны и лежат в пределах от 0 до [latex]K-1[/latex], то эта нумерация определяет полный порядок. Иначе порядок неполный.
- Номер некоторого символа превысил [latex]K-1[/latex]. Это произошло потому, что рост номеров неограничен, т.е. осуществляется циклически. Следовательно порядок противоречив.
Легко понять, что число просмотров не превысит [latex]N[/latex].
Некоторые аспекты реализации
Нам необходимо будет несколько раз просматривать все пары, поэтому их не получится обрабатывать поточно. Будем хранить их в отдельном двумерном массиве.
Воспользуемся тем фактом, что символы воспринимаются компьютером, как числа. Заведем для номеров символов в последовательности массив chars на 256 элементов, поскольку тип данных char может принимать значения от 0 до 255. Это позволит обращаться к элементу массива, соответствующий какому-то символу напрямую, а не используя ассоциативный массив. Это дает выигрыш в скорости, хотя и с некоторым увеличением расхода памяти.
Изначально каждый элемент массива chars пусть будет равен -1. Затем, пройдя все пары, присвоим каждому символу номер 0 в этом массиве. Таким образом, мы в дальнейшем сможем определить, что символ входит в нашу последовательность, поскольку его номер неотрицательный.
Если при очередном просмотре входной строки не произошло изменений, отсортируем массив номеров и проверим каждый ли предыдущий неотрицательный меньше следующего на 1.