题目为中文, 这里就不描述题意了
思路:
从题目陈述来看, 他将一个有向图用一个邻接矩阵来表示, 并且分为两个图 PQ, 但是它们是有内在联系的, 即: P+Q, 抛去方向即为完全图
题目都是中文, 这里就不翻译了我们可以从题目中知道, 如果 PQ 均满足传递性, 那么 P 与 (Q 的反向图) 生成的有向图应该无环
所以, 简单一个拓扑排序检查是否有环即可, PQ 合为一张图, 跑一遍, 这个还是很快的
时长: 3432MS
代码如下:
- #include <iostream>
- #include <stdio.h>
- #include <queue>
- #include <vector>
- using namespace std;
- vector<int> edge[2017];
- queue<int> Q;
- int m, n, inDegree[2017];
- int main()
- {
- scanf("%d\n", &n);
- while (n--)
- {
- scanf("%d\n", &m);
- memset(inDegree, 0, sizeof inDegree);
- for (int i = 1; i<=m; i++) edge[i].clear();
- while (!Q.empty()) Q.pop();
- for (int i = 1; i <= m; ++i)
- for (int j = 1; 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 = 1; i<=m; i++)
- if (!inDegree[i])
- Q.push(i);
- int cnt = 0, newP;
- while (!Q.empty()) {
- newP = Q.front(), Q.pop();
- cnt++;
- for (int i = 0; i<edge[newP].size(); i++) {
- inDegree[edge[newP][i]]--;
- if (inDegree[edge[newP][i]] == 0)
- Q.push(edge[newP][i]);
- }
- }
- if (cnt == m) printf("T\n");
- else printf("N\n");
- }
- }
来源: http://www.bubuko.com/infodetail-2510884.html