nyoj 349 (poj 1094) (拓扑排序)

Sorting It All Out

时间限制：3000 ms | 内存限制：65535 KB

难度：3

描述: 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 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.

输出

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.

样例输入

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 个字母， 且字母由A开始到 char('A' + n - 1)

         Ⅱ、 数据 m 表示有 m 个输入， 用来判断是否能够确定前 n 个字符的关系

         Ⅲ、如果确定其前 n 个字母的先后顺序就输出，同时对后面的数据不做判断

         Ⅳ、如果能够确定有环的存在也可以不用对后面的数据进行判断 （输出 Inconsistency...）

 **/

核心代码：

 int topo_sort () {

     int flag = , temp [], c = , Q[], in_num, pos;

     for (int i = ; i <= n; ++ i) {

         temp [i] = my_in [i];

     }

     for (int i = ; i <= n; ++ i) {

         in_num = ;

         for (int j = ; j <= n; ++ j) {

             if (!temp [j]) {

                 pos = j;

                 in_num ++;

             }

         }

         if (!in_num) return ; // 环

         if (in_num > ) flag = -; // 不可能有序，但有可能有环，所以不能return

         Q [c ++] = pos;

         temp [pos] = -;

         for (int j = ; j <= n; ++ j) {

             if (my_map [pos][j] == ) {

                 temp [j] --;

             }

         }

     }

     return flag;

 }

C/C++代码实现（AC）:

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 int n,     m, my_map [][], my_in [], Q[], c;

 int topo_sort () {

     int flag = , temp [], num_in, pos;

     c = ;

     for (int i = ; i <= n; ++ i) {

         temp [i] = my_in [i];

     }

     for (int i = ; i <= n; ++ i) {

         num_in = ;

         for (int j = ; j <= n; ++ j) {

             if (!temp [j]) {

                 ++ num_in;

                 pos = j;

             }

         }

         if (!num_in) return ; // 环

         if (num_in > ) flag = -; // 不能确定

         temp [pos] = -;

         Q [c ++] = pos;

         for (int j = ; j <= n; ++ j) {

             if (my_map [pos][j] == ) {

                 temp [j] --;

             }

         }

     }

     return flag;

 }

 int main () {

     while (scanf ("%d%d", &n, &m), n !=  || m != ) {

         int flag = , a1, b1;

         char a, b, d;

         memset (my_map, , sizeof (my_map));

         memset (my_in, , sizeof (my_in));

         for (int i = ; i <= m; ++ i) {

             getchar ();

             scanf ("%c%c%c", &a, &d, &b);

             if (!flag) continue;

             a1 = int (a - 'A' + );

             b1 = int (b - 'A' + );

             my_map [a1][b1] = ;

             my_in [b1] ++;

             int x = topo_sort ();

             if (x == ) {

                 printf("Sorted sequence determined after %d relations: ",i);

                 for (int i = ; i < c; ++ i) {

                     printf ("%c", 'A' + Q [i] - );

                 }

                 printf (".\n");

                 flag = ;

             } else if (x == ) {

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

                 flag = ;

             }

         }

         if (flag) {

             printf("Sorted sequence cannot be determined.\n");

         }

     }

 }

巴特西

nyoj 349 (poj 1094) (拓扑排序)

Sorting It All Out

最新文章

热门文章