有向图的拓扑排序

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
int n;
int e[100][100];
vector<int>vec;
int cnt[100];//记录每个节点的入度
int que[200];
int front=0;int tail=0;
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {scanf("%d",&e[i][j]);if(e[i][j])cnt[j]++;}
    for(int i=n-1;i>=0;i--)if(cnt[i]==0)que[tail++]=i;
    int now;
    while(front<tail)
    {
        now=que[front++];vec.push_back(now);
        for(int i=n-1;i>=0;i--)
        {
            if(e[now][i]){cnt[i]--;if(cnt[i]==0)que[tail++]=i;}
        }
    }  
    if(vec.size()<n){printf("ERROR
");}//存在回路
    else {
        for(int i=0;i<vec.size();i++)printf("%d ",vec[i]);
        printf("
");
    }
    return 0;
}

原文地址:https://www.cnblogs.com/linruier/p/10035289.html