小哈哈

用户名：20180390139

访问量：17698

签　名：

世界上怎么会有那么聪明的人呢？

等　　级
排　　名	217
经　　验	6128
参赛次数	9
文章发表	38
年　　龄	0
在职情况	学生
学　　校	蓝翔挖掘机技校
专　　业	网络工程

　　自我简介：

我是个傻嗨，但是我会努力像个正常人

TA的其他文章

校门外的树（C++代码）------两种解法，复杂点的“并查集”和简单的“数组标记”
浏览：268

蓝桥杯2013年第四届真题-大臣的旅费-题解(C++代码)--------------------重点是这个结论，知道后就很简单了
浏览：353

蓝桥杯2015年第六届真题-赢球票-题解(C++代码)-------------队列的出队入队，很简单的
浏览：293

你可能喜欢

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

　　作者: 小哈哈　　　　发表时间：2019-11-21 17:22:03 浏览：745　|　评论：1　

原题链接：数据结构-有向无环图的拓扑排序

这道题看起来啃爹，但是咱们一起来探索一下吧，别看我代码很长，其实不难的。先给你讲个  “鬼”  故事，记得先看完故事再看代码，这样会简单。
	
	   这道题其实在讲一个故事，有个人叫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;
    }

0.0分

5 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

　　评论区

Lay

？

2019-12-29 18:40:19

小哈哈

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

采药（C++代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言考试练习题_排列（C++代码）

C二级辅导-同因查找（C语言代码）

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

评论区

精彩推荐

字符串输入输出函数（Java代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

核桃的数量（C语言代码）

2^k进制数（C语言描述，蓝桥杯）

A+B for Input-Output Practice (I) （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

字符删除（C语言代码）

小哈哈

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

采药 （C++代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言考试练习题_排列 （C++代码）

C二级辅导-同因查找 （C语言代码）

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

评论区

精彩推荐

字符串输入输出函数 （Java代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

核桃的数量 （C语言代码）

2^k进制数 （C语言描述，蓝桥杯）

A+B for Input-Output Practice (I) （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

字符删除 （C语言代码）

采药（C++代码）

C语言考试练习题_排列（C++代码）

C二级辅导-同因查找（C语言代码）

　　评论区

字符串输入输出函数（Java代码）

核桃的数量（C语言代码）

2^k进制数（C语言描述，蓝桥杯）

字符删除（C语言代码）