题意

给定一个有向无权图，问图中是否有环。

思路

用Floyd的形式进行预处理。eg[i][j]不仅仅表示有一条边连着i和j，而表示有一条i到j的路。
这样处理之后遍历所有的情况，如果发现正着和反着都可以，那就是存在环了。

代码

#include 
   
     const int maxn = 55; int n; bool eg[maxn][maxn]; int main() { //freopen("in.txt","r",stdin); int t; scanf("%d",&t); while(t--) { for(int i = 0 ; i < maxn ; i ++) { for(int j = 0 ; j < maxn ; j ++) eg[i][j] = false; } int c; scanf("%d%d",&n,&c); while(c--) { int a,b; scanf("%d%d",&a,&b); eg[a][b] = true; } for(int k = 0 ; k < n ; k ++) { for(int i = 0 ; i < n ; i ++) { for(int j = 0 ; j < n ; j ++) { if(eg[k][i] && eg[i][j]) eg[k][j] = true;//所有可能的路都已经显示出来了 } } } bool flag = false; for(int i = 0 ; i < n ; i ++) { for(int j = 0 ; j < n ; j ++) { if(eg[i][j] && eg[j][i]) { flag = true; break; } } if(flag) break; } if(flag) printf("YES\n"); else printf("NO\n"); } return 0; }