1094. Sorting It All Out

An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.

Input. Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 ≤ n ≤ 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.

Output. For each problem instance, output consists of one line. This line should be one of the following three:

· Sorted sequence determined after xxx relations: yyy...y.

· Sorted sequence cannot be determined.

· Inconsistency found after xxx relations.

where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy...y is the sorted, ascending sequence.

Sample input	Sample output
4 6 A<B A<C B<C C<D B<D A<B 3 2 A<B B<A 26 1 A<Z 0 0	Sorted sequence determined after 4 relations: ABCD. Inconsistency found after 2 relations. Sorted sequence cannot be determined.

РЕШЕНИЕ

топологическая сортировка

Анализ алгоритма

Заведем граф из n вершин. Поскольку каждой вершине соответствует одна заглавная буква, то n ≤ 26. Каждому отношению вида A < B поставим в соответствие ориентированную дугу графа A → B. Последовательно читаем соотношения между буквами, добавляя в граф по одному ребру. После добавления очередного ребра построим топологическую сортировку графа. Возможны случаи:

· топологической сортировки не существует, так как присутствует цикл в графе. В этом случае не все вершины будут добавлены в результирующий массив.

· топологическая сортировка существует. Но необходимо проверить, уникальна ли она. Сортировка будет единственной, если на каждой итерации очередь содержит не более одного элемента.

Реализация алгоритма

#include <cstdio>

#include <deque>

#include <vector>

using namespace std;

vector<vector<int> > graph;

vector<int> InDegree;

int i, n, m;

char a, b, sign, top[30];

int TopSort(void)

{

int i, v, to, ptr = 0;

vector<int> Degree = InDegree;

deque<int> q;

for(i = 0; i < Degree.size(); i++)

if (Degree[i] == 0) q.push_back(i);

int unique = 1;

while(!q.empty())

{

if (q.size() > 1) unique = 0;

v = q.front(); q.pop_front();

top[ptr++] = v + 'A';

for(i = 0; i < graph[v].size(); i++)

{

to = graph[v][i];

Degree[to]--;

if(Degree[to] == 0) q.push_back(to);

}

}

top[ptr] = 0;

int res = 0; // top sort is not unique

if (ptr < n) res = -1; // loop found, inconsistent

else if (unique == 1) res = 1; // unique top sort

return res;

}

int main(void)

{

while(scanf("%d %d\n",&n,&m), n + m)

{

graph.assign(n,vector<int>());

InDegree.assign(n,0);

int flag = 0;

for(i = 0; i < m; i++)

{

scanf("%c%c%c\n",&a,&sign,&b);

graph[a - 'A'].push_back(b - 'A');

InDegree[b - 'A']++;

flag = TopSort();

if (flag != 0) break;

}

if (flag == 1)

printf("Sorted sequence determined after %d relations:

%s.\n",i+1,top);

else

if (flag == 0) printf("Sorted sequence cannot be determined.\n");

else

printf("Inconsistency found after %d relations.\n",i+1);

for(i++; i < m; i++)

scanf("%c%c%c\n",&a,&sign,&b);

}

return 0;

}