Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2478 Accepted Submission(s): 1011
对于两个任何两个点都会有一条边将他们相连（Ai,j ≠ Aj,i）
假设目前有一个环大于3，其中有相连的三个点A,B,C，即 A->B,B->C
如果C->A 有一条边，就形成了一个3环
如果C->A 没有边，那么一定有 A->C，从而形成一个n-1环，以这种方式一定可以形成一个3环
所以只要判断这些点构成一个环即可
1 #include<string> 2 #include<cstdio> 3 #include<iostream> 4 #include<vector> 5 #include<queue> 6 #include<stack> 7 #include<algorithm> 8 #include<cstring> 9 #include<stdlib.h> 10 #include<string> 11 #include<cmath> 12 using namespace std; 13 #define pb push_back 14 vector<int >p[10010]; 15 int in[10010],n,m,deep[10010],num[10010]; 16 char dp[2010][2010]; 17 void init(){ 18 memset(in,0,sizeof(in)); 19 memset(deep,0,sizeof(deep)); 20 memset(num,0,sizeof(num)); 21 for(int i=0;i<=n;i++) p[i].clear(); 22 } 23 int tuopu(){ 24 queue<int >ak_47; 25 int cnt=0; 26 for(int i=1;i<n;i++) 27 if(in[i]==0) ak_47.push(i),deep[i]=1,num[1]++; 28 while(!ak_47.empty()){ 29 int pos=ak_47.front(); 30 cnt++; 31 for(int i=0;i<p[pos].size();i++){ 32 int to=p[pos][i]; 33 if(--in[to]==0) ak_47.push(to),deep[to]=deep[pos]+1,num[deep[to] ]++; 34 } 35 ak_47.pop(); 36 } 37 if(cnt<n) return 1; 38 else return 0; 39 40 } 41 int main(){ 42 int cas=0,t; 43 cin>>t; 44 while(t--){ 45 cin>>n; 46 init(); 47 for(int i=1;i<=n;i++){ 48 scanf("%s",dp[i]); 49 for(int j=0;j<n;j++) 50 if(dp[i][j]==‘1‘) in[j+1]++,p[i].pb(j+1); 51 } 52 if(tuopu()) printf("Case #%d: Yes\n",++cas); 53 else printf("Case #%d: No\n",++cas); 54 } 55 }
原文：http://www.cnblogs.com/ainixu1314/p/3896049.html