本题链接：点击打开链接
本题大意：
题意分析(转载)：此题可以一遍拓扑排序判环求解 即只需要找到一个环，就必定存在三元环 证明如下： 假设存在一个n元环，因为a->b有边，b->a必定没边，反之也成立所以假设有环上三个相邻的点a-> b-> c,那么如果c->a间有边，就已经形成了一个三元环，如果c->a没边，那么a->c肯定有边，这样就形成了一个n-1元环。。。。所以只需证明n大于3时一定有三元环即可，显然成立。
具体请参见代码：
#include<stdio.h>#include<string.h>using namespace std;char map[2010][2010];//存放两节点的关系1:i love j int degree[2010];//存放节点入度 void toposort(int m){int flag=0;for(int i=1;i<=m;i++)//对每个点进行查找 {int j=0;while(degree[j])//找入度为0的点j++;if(j==m)//表明未找到，说明存在环{flag=1;break;}else{degree[j]=-1;//若找到，将入度标为-1for(int k=0;k<m;k++)//把此点引起的点的入度自减一次{if(map[j][k])degree[k]–;}}}if(flag)//存在环，表明存在三角恋printf("Yes\n");elseprintf("No\n");}int main(){int n,m,t=0;scanf("%d",&n);while(n–){memset(map,0,sizeof(map));memset(degree,0,sizeof(degree));scanf("%d",&m);for(int i=0;i<m;i++){scanf("%s", map[i]);for(int j=0;j<m;j++){if(map[i][j]=='1')//若i love j 把j入度自加一次{degree[j]++;}}}printf("Case #%d: ",++t);toposort(m);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，天下爱情，大抵如斯。
