问题标题: 酷町堂：算法讲解4：拓扑排序

拓扑排序：利用有向图按照一定的先后次序做事情

[排序方法]：每次寻找入度为0的节点，将该节点的入度标记为-1并计数，然后寻找该节点的所有出边到达的终点，剪断这些出边( 出边到达的终点的入度减1 )然后循环寻找下一个入度为0的节点，知道没有入度为0的节点。如果发现记录的节点数量少于总节点数，则代表图中存在环

读入边时用邻接矩阵&前向星

#include<iostream>
using namespace std;
int cnt,n,m,head[10001],num;//num:判断有没有环 
int ru[10001];//拓扑排序需要的入度标记,-1代表用过 
struct node{int to,w,next;};
node bian[10001];
void add(int x,int y,int w){//前向星
    cnt++;
    bian[cnt].to=y;
    bian[cnt].w=w;
    bian[cnt].next=head[x];
    head[x]=cnt;
} 
int zhao(){//在图中找入度为0的顶点下标 
    for(int i=1;i<=n;i++)
        if(ru[i]==0)return i;
    return 0;
}   
void tuopu(){//拓扑排序 
    int x=zhao();//先找入度为0的点x 
    if(x==0)return ; //找不到了
    cout<<"拓扑顶点:"<<x<<endl;num++;//记录用于判断有没有环 
    ru[x]=-1;//标记入度为-1，避免下次还找到x
    for(int k=head[x];k;k=bian[k].next)//前向星扫描x的出边,对印的入度减1  
        ru[bian[k].to]--; //断掉x的出边
    tuopu();//等上面所有x的出边都断完了,继续拓扑,一直找到没有为止 
}
int main(){
    int x,y,w;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>w;
        add(x,y,w);
        ru[y]++; //赋值入度 
    } 
    tuopu();
    if(num<n)cout<<"图中有环";
    return 0;
}

许金夫在2021-08-24 17:04:19追加了内容

感谢 @吕若朴 的赞助

日常打广告https://www.luogu.com.cn/blog/Luogu-Blog-Org/点击进入博客