图结构练习――判断给定图是否存在合法拓扑序列(拓扑排序判断环) - c++编程基础

图结构练习――判断给定图是否存在合法拓扑序列

Time Limit: 1000MS Memory limit: 65536K

题目描述

给定一个有向图，判断该有向图是否存在一个合法的拓扑序列。

输入

输入包含多组，每组格式如下。第一行包含两个整数n，m，分别代表该有向图的顶点数和边数。(n<=10) 后面m行每行两个整数a b，表示从a到b有一条有向边。

输出

若给定有向图存在合法拓扑序列，则输出YES；否则输出NO。

示例输入

示例输出

YES
NO

提示

来源

赵利强

示例程序

#include 
  
   
#include 
   
     #include 
    
      int n,m; int map[20][20]; int in[20]; void topo() { int i,j,k; int flag; for(i=1;i<=n;i++) { flag=0; for(j=1;j<=n;j++) { if(in[j]==0) { flag=1;//只要有入度为零的点就变成1 in[j]=-1;//删除这个结点 for(k=1;k<=n;k++)//与该节点相连的的结点的入度-1 { if(map[j][k]) in[k]--; } break;//找到一个入度为零的就结束 } } if(flag==0)//如果结点未输出完，图中就没有了入度为零的结点，证明有环，则不合法 break; } if(flag==1) printf("YES\n"); else printf("NO\n"); } int main() { int u,v,i,j; while(~scanf("%d %d",&n,&m)) { memset(map,0,sizeof(map)); memset(in,0,sizeof(in)); while(m--) { scanf("%d %d",&u,&v); map[u][v]=1; in[v]++; } topo(); } return 0; }