Advertisement

数据结构实验之图论十:判断给定图是否具有合法拓扑序列

阅读量:

【问题描述

针对一个有向图,判断该图是否能够生成一个有效的拓扑排序序列。
输入

输入数据包含多个测试用例,每个用例的格式如下。
第一行给出两个整数n和m,分别表示该有向图中的顶点数量与边的数量。(n<=10)
接下来的m行中,每行包含两个整数a和b,表示从顶点a到顶点b存在一条有向边。

输出

如果给定的有向图中存在有效的拓扑排序序列,则输出YES;否则输出NO。

示例输入

1 0
2 2
1 2
2 1
示例输出

YES
NO

图中存在有效的拓扑排序序列等价于该图不包含任何环状结构。

整体算法通过三层循环实现:第一层用于查找当前入度为零的节点;第二层用于删除该节点所发出的所有边;第三层则用于再次寻找新的入度为零的节点,并重复这一过程。

复制代码
    //1、输入并用邻接矩阵保存点与点之间的关系,用数组保存每个点的入度。
    
    //2、每次找一个入度为零的点,将所有和他相连的点的入度减一(删除相连的边)。
    
    //3、重复步骤二,直到没有入度为零的点为止。
    
    //4、如果这时还有入度不为零的点,证明有环,输出NO,反之输出YES。
    
    
      
      
      
      
      
      
      

全部评论 (0)

还没有任何评论哟~