传递 hdu 5961 拓扑排序有无环~

题目：http://acm.hdu.edu.cn/showproblem.php?pid=5961

题目为中文，这里就不描述题意了。

思路：

从题目陈述来看，他将一个有向图用一个邻接矩阵来表示，并且分为两个图P、Q，但是它们是有内在联系的，即：P+Q，抛去方向即为完全图。

题目都是中文，这里就不翻译了。我们可以从题目中知道，如果P、Q均满足传递性，那么P与（Q的反向图）生成的有向图应该无环。

所以，简单一个拓扑排序检查是否有环即可，P、Q合为一张图，跑一遍，这个还是很快的。

时长：3432MS

代码如下：

 #include <iostream>

 #include <stdio.h>

 #include <queue>

 #include <vector>

 using namespace std;

 vector<int> edge[];

 queue<int> Q;

 int m, n, inDegree[];

 int main()

 {

     scanf("%d\n", &n);

     while (n--)

     {

         scanf("%d\n", &m);

         memset(inDegree, , sizeof inDegree);

         for (int i = ; i<=m; i++)     edge[i].clear();

         while (!Q.empty())     Q.pop();

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

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

             {

                 char ch;

                 cin >> ch;

                 if (ch == 'P')

                     inDegree[j]++, edge[i].push_back(j);

                 if (ch == 'Q')

                     inDegree[i]++, edge[j].push_back(i);

             }

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

             if (!inDegree[i])

                 Q.push(i);

         int cnt = , newP;

         while (!Q.empty()) {

             newP = Q.front(), Q.pop();

             cnt++;

             for (int i = ; i<edge[newP].size(); i++) {

                 inDegree[edge[newP][i]]--;

                 if (inDegree[edge[newP][i]] == )

                     Q.push(edge[newP][i]);

             }

         }

         if (cnt == m) printf("T\n");

         else printf("N\n");

     }

 }

感谢您的阅读，生活愉快~