/***************************参考自****************************/
http://www.cnblogs.com/newpanderking/archive/2012/10/16/2726757.html
上有详细注解，我是看了之后写的，我的代码有一咪咪的改动
//这是一道典型的拓扑排序的题，刚开始时没有理解，
//上网查了好多关于拓扑排序的知识才明白，
//就是针对一个顶点活动网(Activity
On Vertex
network)，简称AOV网，
//从中去除入度为0的顶点，同时更新从改点出发引起的入度，
//让这些点的入度减1，直到最后如果AOV网为空时，
//说明那么去除的这些点就组成了一个拓扑排序，
//如果AOV网不为空，这种情况若在程序中出现，
//则称为死锁或死循环（即形成环），是应该必须避免的，
//说明这些活动是永远执行不到的（在此题中是Yes）。
//（活动的前驱又是在活动之后执行）
/***********************************************************/
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; char love[2010][2010]; int in_degree[2010]; int flag; int tuopu(int n) { int i,j,jj; for(i=0;i<n;i++) { for(j=0;j<n;j++) { if(in_degree[j]==0) { in_degree[j]=-1; break; } } if(j==n) { return 1; } else { for(jj=0;jj<n;jj++) { if(love[j][jj]==‘1‘) in_degree[jj]--; } } } return 0; } int main() { int t,i,j,n,id; scanf("%d",&t); for(id=1;id<=t;id++) { memset(in_degree,0,sizeof(in_degree)); memset(love,‘0‘,sizeof(love)); scanf("%d",&n); for(i=0;i<n;i++) { scanf("%s",love[i]); for(j=0;j<n;j++) if(love[i][j]==‘1‘) in_degree[j]++; } flag=tuopu(n); printf("Case #%d: ",id); if(flag==1)printf("Yes\n"); else printf("No\n"); } return 0; }
//其实我原本是为了搜强连通分量的，然后搜到了这道题；也就是说，这题也可以用 强连通 来做