首页 > 代码库 > 拓扑排序
拓扑排序
问题:给定几组单向边,判断是否可以拓扑排序。
输入:n 全局变量,表示点数
g 全局变量,g[i]表示从点 i 连出去的边
输出:返回对给定的图,是否可以拓扑排序。
L全局变量,拓扑排序的结果
#include <iostream>#include <cstdio>#include <cstring>#include <vector>#include <queue>using namespace std;const int maxn=105;vector <int> g[maxn];int du[maxn],n,m,L[maxn];int toposort(){ int i,j; memset(du,0,sizeof(du)); for(i=1; i<=n; i++) for(j=0; j<g[i].size(); j++) du[g[i][j]]++; int tot=0; queue <int> Q; for(i=0; i<n; i++) if(!du[i])Q.push(i); while(!Q.empty()) { int x=Q.front(); Q.pop(); L[tot++]=x; for(j=0; j<g[x].size(); j++) { int t=g[x][j]; du[t]--; if(!du[t]) Q.push(t); } } if(tot==n)return 1; else return 0;}int main(){ int i,j; while(scanf("%d%d",&n,&m)!=EOF) { for(i=1; i<=100; i++)g[i].clear(); for(i=1; i<=m; i++) { int a,b; scanf("%d%d",&a,&b); g[a].push_back(b); } if(toposort())printf("RIGHT\n"); else printf("ERROR\n"); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。