参考博客
https://blog.csdn.net/lisonglisonglisong/article/details/45543451
代码
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define VerNum 1002
struct node {
int verIdx;*//终点*
int cost;
node(int v1 = 0, int c1 = 0) :verIdx(v1), cost(c1){
}
};
vector<node> g[VerNum];
int n,e;
int ind[VerNum] = { 0 }, topSort[VerNum], cnt = 0;*//拓扑排序用到的数据*
int main(){
int x,y,e,i;
cout<<"请分别输入顶点数和边数:";
cin>>n>>e;
cout<<"请输入边的信息:"<<endl;
for(int i=0;i<e;i++){
cin>>x>>y;
g[x].push_back(node(y));
ind[y]++;
}
*//拓扑排序*
queue<int> q;
for(i=0;i<n;i++){//先找到起点
if(ind[i]==0)
q.push(i);
}
while(!q.empty()){
x=q.front();
q.pop();
topSort[cnt++]=x;
for(i=0;i<g[x].size();i++){
y=g[x][i].verIdx;
ind[y]--;
if(ind[y]==0)
q.push(y);
}
}
if(cnt<n)
cout<<"该有向图有环路"<<endl;
return 0;
}
注意:
用的是queue不是stack
近期评论