定义
一共有好多件事情 事情A要再事情B（或者更多）事情做完才能做 然后排序！（有向无环图）
思路
一个网上找的图便于理解（下列过程以此图为例）
记录所有点的入度和出度找到入度为0的点加入栈中 为a栈顶元素输出删除并把与栈顶元素相连的点的入度减一删除过程中如果有入度为零的点也加入栈中直到输出的数等于n完成排序
PS：如果输出的数小于n 说明此图有环
例题
家谱树 【题目描述】 有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。 给出每个人的孩子的信息。 输入一个序列，使得每个人的后辈都比那个人后列出。 【输入】 第一行一个整数（1<=N<=100），表示家族的人数。 接下来N行，第I行表示第I个人的儿子。 每行最后是0表示描述完毕。 【输出】 输出一个序列，使得每个人的后辈都比那个人后列出。 如果有多解输出任意一解。 【输入样例】 5 0 4 5 1 0 1 0 5 3 0 3 0 【输出样例】 2 4 5 3 1
代码
#include<iostream>
using namespace std;
int a[101][101];//每个点连接的下一个点
int c[101];//出度
int r[101];//入度
int ans[101];//栈
int i,j,tot,temp,num,n;
int main()
{
cin>>n;
for(i=1;i<=n;i++)
{
do
{
cin>>j;
if(j!=0)
{
c[i]++;//i的入度加一
a[i][c[i]]=j;//i的第c[i]个连接点为j
r[j]++;//j的入度加一
}
}
while(j!=0);
}
for(i=1;i<=n;i++)
if(r[i]==0)
ans[++tot]=i;//如果有点入度为0 加入栈中
while(num!=n)//当输出的数不为n是循环
{
temp=ans[tot];//temp等于栈顶的点
cout<<temp;//输出
tot--;//栈中元素减一
num++;//输出数加一
for(i=1;i<=c[temp];i++)//循环与栈顶元素相连的点
{
r[a[temp][i]]--;//入度减一
if(r[a[temp][i]]==0)//如果入度为0 加入栈中
ans[++tot]=a[temp][i];
}
}
}
转载于:https://www.cnblogs.com/BrokenString/p/9279508.html
相关资源：JAVA上百实例源码以及开源项目
