本文共 3122 字，大约阅读时间需要 10 分钟。
原题链接；
这道题看起来啃爹，但是咱们一起来探索一下吧，别看我代码很长，其实不难的。先给你讲个 “鬼” 故事，记得先看完故事再看代码，这样会简单。 这道题其实在讲一个故事，有个人叫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 using namespace std;#include //这是栈的头文件，小伙伴如果不想写栈可以用这个东西哦#define N 100typedef 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 >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 S; //这是一个栈的定义，来自于#include ，例如对于stack 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
转载地址：http://fyfen.baihongyu.com/