sdut原题链接
图结构练习——判断给定图是否存在合法拓扑序列 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description 给定一个有向图，判断该有向图是否存在一个合法的拓扑序列。
Input 输入包含多组，每组格式如下。 第一行包含两个整数n，m，分别代表该有向图的顶点数和边数。(n<=10) 后面m行每行两个整数a b，表示从a到b有一条有向边。
Output 若给定有向图存在合法拓扑序列，则输出YES；否则输出NO。
Example Input 1 0 2 2 1 2 2 1
Example Output YES NO
Hint
Author 赵利强
以下为accepted代码
#include <stdio.h>#include <string.h>int op, tp, n, m;int link[14], map[14][14], indegree[14];//拓扑排序算法核心语句void topo(){ for(int i = 1; i <= n; i++)//寻找入度为零的点 { if(indegree[i] == 0)//判断是否是入度为零的点 link[tp++] = i;//将入度为零的点入队 } while(op < tp)//更新的过程 { for(int i = 1; i <= n; i++)//寻找入度为当前队列结点的点的点 { if(map[link[op]][i] == 1)//判断是否入度为当前队列结点 { indegree[i]--;//结点入度数目更新 if(indegree[i] == 0)//判断更新后是否有入度为零的点 link[tp++] = i;//将更新后入度为零的点入队 } } op++;//当前队列结点出队 } if(op == n)//判断出队结点数是否是总结点数，若是，则为合法拓扑序列，若不是，则存在有向回路 printf("YES/n"); else printf("NO/n");}int main(){ int u, v; while(scanf("%d %d", &n, &m) != EOF) { op = tp = 0;//队列标记变量初始化 memset(map, 0, sizeof(map));//map数组初始化 memset(indegree, 0, sizeof(indegree));//indegree数组（记录结点入度数目）初始化 for(int i = 1; i <= m; i++) { scanf("%d %d", &u, &v); map[u][v] = 1; indegree[v] += 1; } topo(); } return 0;}/***************************************************User name: Result: AcceptedTake time: 0msTake Memory: 108KBSubmit time: 2017-02-20 09:37:18****************************************************/新闻热点
疑难解答
