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

Description
给定一个有向图，判断该有向图是否存在一个合法的拓扑序列。
Input
输入包含多组，每组格式如下。
第一行包含两个整数n，m，分别代表该有向图的顶点数和边数。(n<=10)
后面m行每行两个整数a b，表示从a到b有一条有向边。

Output
若给定有向图存在合法拓扑序列，则输出YES；否则输出NO。
Sample
Input
1 0
2 2
1 2
2 1
Output
YES
NO

Tip:
AOV网与AOE网
分开说：
拓扑排序
AOE网关键路径

//one #include<bits/stdc++.h>using namespace std;int mp[25][25];//建立图 int in[25];//记录入度 int q[111];//用数组模拟队列来做的int main() {int n, m;while(cin >> n >> m){memset(mp, 0, sizeof(mp));//清空图memset(in, 0, sizeof(in));//清空入度int head = 0, tail = 0;//清空队列while(m--)//建图{int u, v;cin >> u >> v;mp[u][v] = 1;in[v]++;//b对应的入度+1}for(int i = 1; i <= n; i++)//找到入度等于0的点{if(!in[i])q[tail++] = i;//入度为0的点入队}int cnt = 0;//计数while(head < tail)//队列不为空{int top = q[head++];//cnt++;in[top]--;//输出点的入度由0变为-1for(int i = 1; i <= n; i++)//删除top的后继{if(mp[top][i]){in[i]--;if(!in[i])//判断入地是否为零q[tail++] = i;//入度为零的入队列}}}if(cnt == n)cout << "YES" << endl;elsecout << "NO" << endl;}return 0; } //two STL队列 #include<bits/stdc++.h>using namespace std;int mp[11][11]; int in[11];void ToList(int n) {queue<int>q;for(int i = 1; i <= n; i++){if(!in[i])q.push(i);}int cnt = 0;while(!q.empty()){int top = q.front();q.pop();cnt++;for(int i = 1; i <= n; i++){if(mp[top][i]){in[i]--;if(!in[i])q.push(i);}}}if(cnt == n)cout << "YES" << endl;elsecout << "NO" << endl; }int main() {int n, m;while(cin >> n >> m){memset(mp, 0, sizeof(mp));memset(in, 0, sizeof(in));while(m--){int u, v;cin >> u >> v;mp[u][v] = 1;in[v]++;}ToList(n);}return 0; }

总结

以上是生活随笔为你收集整理的数据结构实验之图论十：判断给定图是否存在合法拓扑序列的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。