题目
我们称一个有向图G是 传递的，当且仅当对任意三个不同的顶点a,,若G中有 一条边从a到b且有一条边从b到c ,则G中同样有一条边从a到c。 我们称图G是一个 竞赛图，当且仅当它是一个有向图且它的基图是完全图。换句 话说，将完全图每条边定向将得到一个竞赛图。 下图展示的是一个有4个顶点的竞赛图。
现在，给你两个有向图P = (V,Ep)和Q = (V,Ee)，满足: 1. EP与Ee没有公共边； 2. (V,Ep⋃Ee)是一个竞赛图。 你的任务是：判定是否P，Q同时为传递的。
Input
包含至多20组测试数据。 第一行有一个正整数，表示数据的组数。 对于每组数据，第一行有一个正整数n。接下来n行，每行为连续的n个字符，每 个字符只可能是’-’,’P’,’Q’中的一种。 ∙如果第i行的第j个字符为’P’，表示有向图P中有一条边从i到j; ∙如果第i行的第j个字符为’Q’，表示有向图Q中有一条边从i到j; ∙否则表示两个图中均没有边从i到j。 保证1 <= n <= 2016，一个测试点中的多组数据中的n的和不超过16000。保证输入的图一定满足给出的限制条件。
Output
对每个数据，你需要输出一行。如果P! Q都是传递的，那么请输出’T’。否则， 请输出’N’ (均不包括引号)。
Sample Input
4
4
-PPP
--PQ
---Q
----
4
-P-P
--PQ
P--Q
----
4
-PPP
--QQ
----
--Q-
4
-PPP
--PQ
----
--Q-
Sample Output
T
N
T
N
Hint
在下面的示意图中，左图为图为Q。
注：在样例2中，P不是传递的。在样例4中，Q不是传递的。
分析
根据题目中的性质可以知道，这是一个没有环的图
因为这个图是任意两点都直接相连的，所以就可以用BFS找出两点之间的距离，大于一则不是完全图
代码
1 #include <cstdio> 2 #include <queue> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 const int maxn = 2100; 7 vector<int> v1[maxn], v2[maxn]; 8 int dis[maxn]; 9 int n, T; 10 char s[maxn]; 11 bool Bfs(int x, vector<int> v[]){ 12 queue<int> q; 13 memset(dis, 0 , sizeof(dis)); 14 q.push(x); 15 while (q.size()){ 16 int jl = q.front(); 17 q.pop(); 18 for (int i = 0; i < v[jl].size(); i++){ 19 int to = v[jl][i]; 20 if (!dis[to]){ 21 if (jl != x) return 0; 22 dis[to] = dis[jl] + 1; 23 q.push(to); 24 if (dis[to] > 1) return 0; 25 } 26 } 27 } 28 return 1; 29 } 30 int main(){ 31 scanf("%d", &T); 32 while (T--){ 33 scanf("%d", &n); 34 for (int i =1; i <= n; i++) 35 v1[i].clear(), v2[i].clear(); 36 for (int i = 1; i <= n; i++){ 37 scanf("%s", s + 1); 38 for (int j = 1; j <= n; j++){ 39 if (s[j] == 'P') v1[i].push_back(j); 40 if (s[j] == 'Q') v2[i].push_back(j); 41 } 42 } 43 bool bj = 1; 44 for (int i = 1; i <= n; i++){ 45 if (!Bfs(i,v1)){ 46 bj = 0; 47 break; 48 } 49 if (!Bfs(i,v2)){ 50 bj = 0; 51 break; 52 } 53 } 54 if (!bj) printf("N "); 55 else printf("T "); 56 } 57 return 0; 58 }