poj 1094 Sorting It All Out 解题报告

题目链接：http://poj.org/problem?id=1094

题目意思：给出 n 个待排序的字母和 m 种关系，问需要读到第几行可以确定这些字母的排列顺序或者有矛盾的地方，又或者虽然具体的字母顺序不能确定但至少不矛盾。这些关系均是这样的一种形式：字母1 < 字母2

　　这道题目属于图论上的拓扑排序，由于要知道读入第几行可以确定具体的顺序，所以每次读入都需要进行拓扑排序来检验，这时每个点的入度就需要存储起来，所以就有了代码中memcpy 的使用了。

拓扑排序的思路很容易理解，但写起来还是需要注意很多细节。参考了别人的代码，第一次写，受益匪浅啊。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <vector>

 #include <queue>

 using namespace std;

 const int maxn =  + ;

 vector<int> vi[maxn];

 queue<int> q;

 int in[maxn], temp[maxn];

 int n, m, cnt;

 char ans[maxn], input[];

 bool check(int x, int y)     // 检查之前是否插入过该边

 {

     for (int i = ; i < vi[x].size(); i++)

     {

         if (vi[x][i] == y)

             return true;

     }

     return false;

 }

 int Toposort()

 {

     while (!q.empty())

         q.pop();

     for (int i = ; i < n; i++) // 将入度为0的点入队

     {

         if (!in[i])

             q.push(i);

     }

     bool unsure = false;

     cnt = ;

     while (!q.empty())    // 取出第一个入度为0的点

     {

         if (q.size() > ) // 假如有n个点的DAG入度为0的点只有一个，那么就可以确定已排好序

             unsure = true;

         int tmp = q.front();

         ans[cnt++] = tmp + 'A';

         q.pop();

         for (int i = ; i < vi[tmp].size(); i++) // 该点引出的边删除

         {

             in[vi[tmp][i]]--;      // 即入度减1

             if (!in[vi[tmp][i]])  // 恰好入度减1后，该点入度变为0

                 q.push(vi[tmp][i]);

         }

     }

     if (cnt < n)   // 有环

         return ;

     if (unsure)    // 有待进一步斟酌

         return ;

     return ;      // 已经排好序

 }

 int main()

 {

     int step, flag;

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

     {

         for (int i = ; i < maxn; i++)

             vi[i].clear();

         bool ok = false;

         memset(in, , sizeof(in));

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

         {

             scanf("%s", input);

             if (ok)

                 continue;

             int l = input[] - 'A';

             int r = input[] - 'A';

             if (!check(l, r))

             {

                 vi[l].push_back(r);

                 in[r]++;

             }

             memcpy(temp, in, sizeof(in));   // 每个点的入度数处理前先拷贝一份以待下一次输入再用

             flag = Toposort();

             memcpy(in, temp, sizeof(temp));

             if (flag != )   // 暂时不能判断属于哪种情况，先保存step数

             {

                 step = i;

                 ok = true;

             }

         }

         if (flag == )

         {

             ans[cnt] = '\0';

             printf("Sorted sequence determined after %d relations: %s.\n", step, ans);

         }

         else if (flag == )

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

         else

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

     }

     return ;

 }

巴特西

poj 1094 Sorting It All Out 解题报告

最新文章

热门文章