数据结构-有向无环图的拓扑排序-题解(C语言代码)--------------讲故事描述

这道题看起来啃爹，但是咱们一起来探索一下吧，别看我代码很长，其实不难的。先给你讲个  “鬼”  故事，记得先看完故事再看代码，这样会简单。
   这道题其实在讲一个故事，有个人叫XH[i],如果他跟XH[j]这个人有关系，
   那肯定是XH[j]被XH[i]打了，这里呢就用A[i][j]表示他们有没有关系，如果A[i][j]=1，就表示他们有关系。另外他们身上都有个标记，表示他被几个人打过，这个标记就是innum，如果XH[i]的innum为0表示这个人他没被人欺负过，他太牛了。另外他们身上还有个标记叫outwith[]表示他们打过谁，打过的人就被标记进他们的outwith[]里面，表示他们的战绩。然后呢，看看谁最牛牛逼，如果他从没被打过，那么他就是最牛逼的，但是你会发现这种人不止一个，怎么办呢，这里就看他们的编号，他们身上还有个标记size表示他们的编号，编号越小，谁就最优先。首先把入度为0（从没被打过）的按编号的最小顺序输出先  入栈 S   ,S是一个栈，但是它也是一个棺材，XH[i]入栈表示他不小心死了，但是 ：比如XH[j]被XH[i]打过，现在XH[i]不小心死了，这时XH[j]身上的标记innum要减减，表示打过他的人少一个了。我们说了，这个人不小心死了，但是他会变成鬼，然后去找那些他之前打过的人，而这些人的名字都在他的outwith[]里面记录着.所以他太坏了，死了还想欺负人家。他第一步是出栈，表示他要跳出棺材，仔细想想刚刚编号小的先进棺材的，所以出棺材的时候是编号小的要后出，编号大的要先出。
   他怎么找呢，可能他打过好几个人啊，原来他是按他打人的先后顺序来找，先找到outwith[0],然后再找outwith[1],再找outwith[2]，因为outwith[]里面记录着那些人的名字。如果他一找到那个人，那他们就“可能”会决斗，但是要怎么判断他们有没有决斗呢，如果XH[j]被XH[i]打过，但是现在XH[j]因为XH[i]死了，XH[j]它的innum也减1了，也就是打过他的人少一个了，这时如果XH[j]的innum为0了，说明XH[j]很牛逼了，也就是打过他的人都死了，竟然这么牛逼XH[i]就会跟他决斗，由于XH[i]已经是一个鬼魂，他很快就把XH[j]给干掉了。这个时候XH[j]的尸体就会被放入S这个栈里面。
   这说明了什么，如果刚刚XH[j]的innum不为0的话，XH[i]就不会跟他决斗了，因为它觉得XH[j]还不够强大，不配跟他打，然后他就找下一个他打过的人XH[j+1],如果没有了怎么办，也就是XH[i]这个鬼已经找完他之前打过的人了，后面因为他的这种无耻的做法激怒了小编，所以小编让他魂飞魄散了。
   接下来S栈里面，也就是这个棺材里面又跑出一个鬼，他会重复XH[i]这个鬼的操作，最后也被小编给编死了......直到这个棺材里面没有鬼了，故事才结束
好了接下来看看小编的代码
#include<iostream>
using namespace std;
#include<stack>   //这是栈的头文件，小伙伴如果不想写栈可以用这个东西哦
#define N 100
typedef struct node{  //这是一个节点的结构体，节点里面有“入度”，和出边，也就是这个节点能到哪个节点。
    int size;  //这里是标记这是那个节点，是第一个还是第二个
    int innum;  //这是记录这个节点的入度为多少，也就是有多少个点可以到它
    int inwith[N];  //这个不用理
    int outwith[N];  //这里是表示这个点能到哪个点，那么就把那个点加进去
}node;
int n;  //这里是有n个点
int main(){
    cin>>n;
    int A[N][N]={0};  //这是存储输入的那个数组
    node XH[N];     //例如XH[2],表示2这个点
    int i,j,k,t;
    for(i=1;i<=n;i++){
        XH[i].innum=0;  //开始要初始化
        XH[i].size=i-1;  //要让XH[i].innum，XH[i].outwith[j]的值为0，因为结构体是不会帮你默认没赋值的东西为0的
        for(j=0;j<n;j++){
            XH[i].outwith[j]=0;
        }
    }
    for(i=1;i<=n;i++){   //这两个循环是输入来的，同时也稍微做点操作
        k=0,t=0;  //同时也记录了这个点的入度啊，和能到的边啊
        for(j=1;j<=n;j++){
            cin>>A[i][j];  //输入一个数据
            if(A[i][j]){  //如果这个数据不是0，那就说明i是可以到j这个点的
                XH[j].innum++;  //因为表示i可以到j,那么j这个点的入度是不是要加1呢，是吧，因为有一个点可以到j了嘛
                XH[i].outwith[t++]=j;//但是i这个点是可以到j的那么就要记录它能到的点，所以把j纳入i里面，其实就是i娶了一个老婆嘛
            }
        }
    }
    stack<node> S;  //这是一个栈的定义，来自于#include<stack> ，例如对于stack<int> S，它是定义一个int型的栈S,那么这里就是定义一个node类型的栈咯
    for(i=1;i<=n;i++){
        if(!XH[i].innum)  //如果这个点的入度为0那么就入栈咯
            S.push(XH[i]);  //这是入栈操作，S是我们刚刚定义的栈，它里面有一个东西叫push(),这个东西是可以压入一个和它相同类型的节点
    }
    int count=0;  //这里是记录有多少个节点 它的度为0
    node temp;  
    int bag[N]={0},gg=0;  //bag[]是存储出栈的节点的，gg只不过是一个普通的变量而已
    while(!S.empty()){  //还记得S吧，我们刚刚定义的，它里面不仅有push()这个东西，还有empty()这个东西，而empty()是判断S栈是否为空
        temp=S.top();  //S栈里面还有个top()，它的作用是获取栈顶元素
        bag[gg++]=temp.size;  //既然栈里面的元素表示度为0的节点，那好了，先获取栈顶元素，把它放进麻袋里，别弄丢了
        S.pop();  //坑爹了，S栈里面还有一个东西叫pop（）,表示弹出栈元素，也就是把这个节点删除
        count++;  //这里也记录一下度为0的节点
        for(i=0;temp.outwith[i]!=0;i++){  //记得temp是刚刚那个出栈的元素，它死了，但是你要保留它的灵魂，因为你要找到它认识的人，然后把关系掐断
            XH[ temp.outwith[i] ].innum--;  //首先temp里面是有一个东西叫outwith[]的，我们在开始的结构体已经定义了，它是存储temp这个点能到的点，也就是temp它搞过哪个男的，这些男的也要被记录进outwith[]里面
            if(!XH[ temp.outwith[i] ].innum)  //如果temp搞过的这个男的，如果这个男的的入度也为0,那么就要入栈
                S.push(XH[ temp.outwith[i] ]);  //把这个被temp搞过的男的，压入栈，因为它的入度为0，也就是它太弱了，它没搞过其他男的
        }
    }
    if(count<n){  //如果度为0的节点不够n个，说明肯定有环啦
    cout<<"ERROR"<<endl;
    }else{
        for(i=0;i<gg;i++){
            if(i!=gg-1)  //这里是确保最后一个数据输出时不含有空格
            cout<<bag[i]<<" ";
            else
                cout<<bag[i]<<endl;
        }
    }
    return 0;
}