题目描述 Description
人们的恋爱关系与如下特点：两个人a，b，如果a爱着b，那么b一定不爱a；如果a不爱b，那么b一定爱着a（yh的研究成果果然与众不同……）。
现在，yh想知道，在n个人当中，是否存在三角恋现象（即a爱着b，b爱着c，c爱着a）。
输入描述 Input Description
本题有多组测试数据
第一行一个整数t，表示有t组测试数据。
对于每组数据，第一行为一个整数n，表示共有n人。
接下来为n*n的0,1矩阵a，如果a[i，j]=1,则i爱着j，否则表示i不爱j;数据保证a[i,j]<>a[j,i]。
输出描述 Output Description
每组数据输出一行，如果存在三角恋，输出’Yes’，否则输出’No’。
样例输入 Sample Input
2
5
00100
10000
01001
11101
11000
5
01111
00000
01000
01100
01110
样例输出 Sample Output
Yes
No
数据范围及提示 Data Size & Hint
对于40%的数据，n≤10
对于100%的数据，n≤2000, t≤5
tarjan算法
#include<cstdio> #include<iostream> #include<stack> #include<vector> #include<cstring> #define M 2016 using namespace std; vector<int> grap[M]; stack<int> s; char ch[M]; int low[M],num[M],vis[M],instack[M],map[M][M],f[M],n,cnt,tot; void tarjan(int v) { low[v]=num[v]=++tot; s.push(v); instack[v]=1; vis[v]=1; for(int i=0;i<grap[v].size();i++){ int w=grap[v][i]; if(!vis[w]){ tarjan(w); low[v]=min(low[v],low[w]); } else if(instack[w]) low[v]=min(low[v],num[w]); } int u; if(low[v]==num[v]){ ++cnt; do { u=s.top(); f[cnt]++; s.pop(); instack[u]=0; }while(u!=v); } } void init(){ int x; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%s",ch); for(int j=1;j<=n;j++) map[i][j]=(int)ch[j-1]-'0'; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(map[i][j]==1)grap[j].push_back(i); for(int i=1;i<=n;i++) if(!vis[i])tarjan(i); if(cnt<n)printf("Yes "); else printf("No "); for(int i=1;i<=n;i++)grap[i].clear(); } int main(){ int t; scanf("%d",&t); for(int i=1;i<=t;i++){ cnt=0; memset(vis,0,sizeof(vis)); memset(low,0,sizeof(low)); memset(num,0,sizeof(num)); memset(instack,0,sizeof(instack)); memset(f,0,sizeof(f)); init(); } return 0; }