首页 > 代码库 > 图结构练习——判断给定图是否存在合法拓扑序列(sdutoj)
图结构练习——判断给定图是否存在合法拓扑序列(sdutoj)
#include<stdio.h>
#include<string.h>
int d[15],map[15][15],vis[15];
int main()
{
int i,j,k,f,n,m,u,v;
while(~scanf("%d%d",&n,&m))
{
memset(d,0,sizeof(d));
memset(map,0,sizeof(map));
memset(vis,0,sizeof(vis));
for(i=1; i<=m; i++)
{
scanf("%d%d",&u,&v);
map[u][v]=1;
d[v]++;
}
for(i=1; i<=n; i++)
{
f=0;
for(j=1; j<=n; j++)
{
if(d[j]==0&&vis[j]==0)
{
vis[j]=1;
for(k=1; k<=n; k++)
if(map[j][k])
d[k]--;
f=1;
break;//找到一个入度为0的就结束
}
}
if(f==0)//如果节点未输出完,而图中就没有了入度为0的节点,则说明有环,不合法。
break;
}
if(f==0)
printf("NO\n");
else
printf("YES\n");
}
}