题意：
分析：显然，对于每个点来说，只要他的能到达的点的能到达的点能到达，他就是合法的，反之就是不合法的
比如
1能到达的点是2,3 1能到达的点能到达的点也就是2,3能到达的点，就是3
因为1能到达3，所以他就是合法的
1能到达的点是2,3 1能到达的点能到达的点也就是2，3能到达的点是3,4
1只能到达3不能到达4，所以不合法
所以其实只需要对每个点搞一遍类似bfs的操作即可
这题常卡的有点死，不能用前向星（head的赋初值较为耗时），要用vector存边
代码：
#include<cstdio> #include<queue> #include<cstring> #include<vector> using namespace std; const int maxm=5e6+1; const int maxn=2017; vector<int> e[maxn][2]; bool vis[maxn]; int n; int bfs(int x,int p) { if(!e[x][p].size()) return 1; memset(vis,0,sizeof(vis)); queue<int> q; for(int i=0;i<e[x][p].size();i++) { int v=e[x][p][i]; vis[v]=1;q.push(v); } while(!q.empty()) { int now=q.front();q.pop(); for(int i=0;i<e[now][p].size();i++) if(!vis[e[now][p][i]]) return 0; } return 1; } int pd() { for(int i=1;i<=n;i++) if(!bfs(i,0)) return 0; for(int i=1;i<=n;i++) if(!bfs(i,1)) return 0; return 1; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=1;i<=n;++i) { char ch=getchar(); e[i][0].clear();e[i][1].clear(); for(int j=1;j<=n;++j) { ch=getchar(); if(ch==‘P‘) e[i][0].push_back(j); else if(ch==‘Q‘) e[i][1].push_back(j); } } putchar(pd()?‘T‘:‘N‘); putchar(‘\n‘); } return 0; }
原文：https://www.cnblogs.com/lin4xu/p/12920275.html