sdut_2140_数据结构实验之图论十：判断给定图是否存在合法拓扑序列

本文主要是介绍sdut_2140_数据结构实验之图论十：判断给定图是否存在合法拓扑序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

数据结构实验之图论十：判断给定图是否存在合法拓扑序列

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic Discuss

Problem Description

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

Input

 输入包含多组，每组格式如下。

第一行包含两个整数n，m，分别代表该有向图的顶点数和边数。(n<=10)

后面m行每行两个整数a b，表示从a到b有一条有向边。

 

Output

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

 

Sample Input

1 0
2 2
1 2
2 1

Sample Output

YES
NO

Hint

Source

赵利强

 

 

拓扑序列，即有向图无环。每次找一个入度为零的点，将所有和它相连的点的入度减一（删除相连的边），重复此步骤直到没有入度为零的点为止。如果这时还有入度不为零的点，证明有环，输出NO，反之输出YES。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>int main()
{int book[11];int map[11][11];int du[11];int n, m, i, j, k, u, v, flag;while(~scanf("%d%d", &n, &m)){memset(book, 0, sizeof(book));memset(map, 0, sizeof(map));memset(du, 0, sizeof(du));if(m == 0)printf("YES\n");else{for(i = 1; i <= m; i++){scanf("%d%d", &u, &v);map[u][v] = 1;du[v]++;}for(i = 1; i <= n; i++) //为什么要进行n次循环呢，因为flag每次都会变成0，但点的入度是在改变的，所以 最重要的是判断最后一次是否还存在着入度不为0 的点{flag = 0;for(j = 1; j <= n; j++)    // 开始找入度为 0 的点{if(!book[j] && !du[j])  //没有标记过且入度为 0 {book[j] = 1;for(k = 1; k <= n; k++)  // 找和它相连的点{if(map[j][k] == 1)du[k]--;          // 入度 -1}flag = 1;break;           //直接进入下一次循环}}}if(flag)printf("YES\n");elseprintf("NO\n");}}return 0;
}

 

这篇关于sdut_2140_数据结构实验之图论十：判断给定图是否存在合法拓扑序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---