hdu4324 拓扑排序

时间:2022-05-05 10:37:41
#include<cstdio>
#include<string.h> #define maxn 2013
char M[maxn][maxn];
int du[maxn]={0};
int que[maxn]={0}; bool topu(int n)//拓扑排序,若存在环,返回false
{
int pos,i,j,cnt=0;
int start=0,end=0;
for( i=0; i< n;i++)
if(du[i]==0)que[end++]=i;
if(start==end )return false; while(start!=end)
{
pos = que[start++];
cnt++;
for(j=0; j<n;j++)
{
if(M[pos][j]=='1')
{
du[j]--;
if(du[j]==0)que[end++]=j;
}
}
}
return cnt==n ? true:false;
} int main()
{
int t,c;
scanf("%d",&t);
for(c=1;c<=t;c++)
{
int n,i,j;
scanf("%d",&n);
memset(du,0,sizeof(du));
for(i=0; i< n;i++)
{
scanf("%s",&M[i]);
for(j=0; j< n;j++)
{
if(M[i][j]=='1')du[j]++;
}
}
if(!topu(n)) printf("Case #%d: Yes\n",c);
else printf("Case #%d: No\n",c);
}
return 0;
}