拓扑排序

拓扑排序是对有向无环图的顶点的一种排序。

// 采用邻接矩阵实现，map[i][j]=0表示无关，map[i][j]=1表示存在有向边<i,j>

#include<iostream>
#include<cstring>
#define N 101
using namespace std;

//顶点的编号为1..n
void topsort(int map[N][N],int indegree[N],int n)
{
    for(int i=0;i<n;i++) //遍历n次，每次输出一个顶点
    {
        for(int j=1;j<=n;j++)
        {
            if(indegree[j]==0)
            {
                if(i==0) cout<<j;
                else cout<<' '<<j;
                indegree[j]--;
                for(int k=1;k<=n;k++)
                {
                    if(map[j][k])
                        indegree[k]--;
                }
                break; //每次找到一个入度为0的点输出即可
            }
        }

    }
}

int main()
{
    int n,m;
    cin>>n;  //n为顶点的个数
    int map[N][N],indegree[N];
    memset(map,0,sizeof(map));
    memset(indegree,0,sizeof(indegree));

    for(int i=0;i<n;i++)
    {
        cin>>m;
        if(m!=0)
        {
            int t;
            while(cin>>t && t)
            {
                map[m][t]=1; //存在一条有向边
                indegree[t]++;
            }
        }
    }
    topsort(map,indegree,n);
    return 0;

}