题目描述
给定一个有向图，判断该有向图是否存在一个合法的拓扑序列。
输入
输入包含多组，每组格式如下。
第一行包含两个整数n，m，分别代表该有向图的顶点数和边数。(n<=10)
后面m行每行两个整数a b，表示从a到b有一条有向边。
输出
若给定有向图存在合法拓扑序列，则输出YES；否则输出NO。
示例输入
1 0
2 2
1 2
2 1
示例输出
YES
NO
1 #include<stdio.h>
2 #include<
string.h>
3 int map[
11][
11],vis[
11],degree[
11];
4 int main()
5 {
6 int n,m,u,v,i,j,k;
7 while(~scanf(
"%d %d",&n,&
m))
8 {
9 memset(map,
0,
sizeof(map));
10 memset(degree,
0,
sizeof(vis));
//每个节点的入度初始为0；
11 while(m--
)
12 {
13 scanf(
"%d %d",&u,&
v);
14 map[u][v] =
1;
15 degree[v]++;
//v的入度加1；
16 }
17 int w,flag =
1;
18 for( i =
1; i <= n; i++
)
19 {
20 w =
0;
//判断是否还有入度为0的点；
21 for( j =
1; j <= n; j++
)
22 {
23 if(degree[j] ==
0)
24 {
25 w =
1;
//若存在入度为0的点，标记为1；
26 degree[j]--;
//删除该顶点
27 for( k =
1; k <= n; k++
)
28 {
29 if(map[j][k])
30 degree[k]--
;
31 }
//删除以该顶点为首的所有有向边，即入度减1；
32 break;
33 }
34
35 }
36 if(w ==
0)
//如果不存在前驱结点了，说明不存在合法拓扑排序；
37 {
38 flag =
0;
39 break;
40 }
41 }
42 if(flag)
43 printf(
"YES\n");
44 else printf(
"NO\n");
45 }
46 return 0;
47 }
View Code
转载于:https://www.cnblogs.com/LK1994/p/3162490.html
相关资源：JAVA上百实例源码以及开源项目
