JakeLin

用户名：jake546

访问量：43185

签　名：

腾讯需要我！

等　　级
排　　名	40
经　　验	13199
参赛次数	3
文章发表	85
年　　龄	21
在职情况	学生
学　　校	华南农业大学
专　　业

　　自我简介：

幸福是奋斗出来的

TA的其他文章

JakeLin-题解1923：蓝桥杯算法提高VIP-学霸的迷宫（C++代码）
浏览：681

迷宫问题-题解(C/C++)-BFS（附图详细解析）
浏览：1652

JakeLin-题解1426：蓝桥杯历届试题-九宫重排（C++代码）
浏览：536

你可能喜欢

C语言程序设计教程（第三版）课后习题10.7 （C++代码）（都说了scanf和gets一般不要混着用）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）如果a<0，那就不是这个代码了，哈哈哈哈

优质题解

JakeLin-1506题-卡勒沃夫之弱水路三千(提高型)-题解(C++代码)-拓扑排序（详细解析+图解）

　　作者: JakeLin　　　　发表时间：2020-02-10 23:12:49 浏览：559　|　评论：1　

原题链接：蓝桥杯算法提高VIP-卡勒沃夫之弱水路三千(提高型)

本题考点为**拓扑排序**，题例如下图：
![](/image_editor_upload/20200210105005_77387.png)
> in表示入度 out表示出度

#### 一、思路
所谓拓扑排序，就是要从拓扑图中找出三个节点的先后顺序，应为：
**tomorrow->today->yesterday**

------------

**拓扑排序**思路相信大家很熟悉了：
- 找到起点：入度为0的节点（tomorrow）
- 访问它（输出它），并将其两个出度边删除（yesterday和today入度减1）
- 找到下一个入度为0的节点，循环往复

------------
#### 二、实现
**1.节点结构体：**

struct node{
    	string s;   //节点名称
    	int in,out;  //入度和出度
    }nn[maxn];
nn[cnt]为一个**结构体数组**，其每一个元素为一个节点。

**2.存储地图：**

map<string,int> nameToindex; //需了解map和vector本质跟数组一样
    vector<int> mapper[maxn];
    int vis[maxn];
变量解释：
nameToindex["today"] = 2:表示名字为today的节点是第2个节点
mapper[2]：是第2个节点所指向的节点组成的数组
vis[2]：表示第2个节点访问过了后续无需访问

**3.构建地图需注意：**
第一次出现这个名字，需新增一个节点，出入度默认为0。
第n次出现这个名字（n>1），只需更新这个节点的出入度即可。

完整代码如下：
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>; 
using namespace std;
const int maxn = 100 + 10;
struct node{
	string s;
	int in,out;  //入度和出度
}nn[maxn];
map<string,int> nameToindex;
vector<int> mapper[maxn];
int vis[maxn];
int cnt;
int main(){
	int n;
	cin>>n;
	while(n--){
		cnt=0; //由于有多组数据，以下四行进行全局变量的初始化
		memset(vis,0,sizeof(vis));
		memset(mapper,0,sizeof(mapper));
		nameToindex.clear();
		int m;
		cin>>m;
		for(int i=0;i<m;i++){
			string s1,s2;
			cin>>s1>>s2;
			int tag1,tag2;
			tag1=tag2=0;
			for(int i=0;i<cnt;i++){//不是第一次出现这个节点，更新节点
				if(nn[i].s == s1){
					tag1=1;
					nn[i].out++;
				}
				if(nn[i].s == s2){
					tag2=1;
					nn[i].in++;
				}
			}
			if(!tag1){//第一次出现名字，新建节点
				nn[cnt].s = s1;
				nn[cnt].out++;
				nameToindex[s1] = cnt;
				cnt++; 
			}
			if(!tag2){
				nn[cnt].s = s2;
				nn[cnt].in++;
				nameToindex[s2] = cnt;
				cnt++;
			}
			mapper[nameToindex[s1]].push_back(nameToindex[s2]);//构建地图（以节点的序号，而不是节点的名字）
		}
		while(m--){  //有m个节点要访问，循环m次
			for(int i=0;i<cnt;i++){  //每次找出入度为0的节点，访问并删去输出边
				if(vis[i]==0 && nn[i].in==0){
					cout<<nn[i].s<<" ";
					vis[i]=1;
					for(int j=0;j<mapper[i].size();j++){ //被访问的点所连接的边入度减1
						nn[mapper[i][j]].in--;
					}					
				}
			}	
		}
		cout<<endl;
	}
	return 0;
}
```

0.0分

7 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

斯巴达

我靠这才是正解, 思路很清晰

2022-03-16 19:05:51

JakeLin

TA的其他文章

你可能喜欢

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

数字整除（C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C++代码）（都说了scanf和gets一般不要混着用）

点我有惊喜！你懂得！

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）如果a<0，那就不是这个代码了，哈哈哈哈

JakeLin-1506题-卡勒沃夫之弱水路三千(提高型)-题解(C++代码)-拓扑排序（详细解析+图解）

评论区

精彩推荐

点我有惊喜！你懂得！

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

蓝桥杯历届试题-九宫重排（C++代码）

数对（C语言代码）

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

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

杨辉三角（C语言代码）

DNA （C语言代码）

计算质因子（C语言代码）

良心推荐——>题解1049：C语言程序设计教程（第三版）课后习题11.1 （C语言描述——简单明了，时间复杂度低）

JakeLin

TA的其他文章

你可能喜欢

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

数字整除 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C++代码）（都说了scanf和gets一般不要混着用）

点我有惊喜！你懂得！

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码） 如果a<0，那就不是这个代码了，哈哈哈哈

JakeLin-1506题-卡勒沃夫之弱水路三千(提高型)-题解(C++代码)-拓扑排序（详细解析+图解）

评论区

精彩推荐

点我有惊喜！你懂得！

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

蓝桥杯历届试题-九宫重排 （C++代码）

数对 （C语言代码）

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

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

杨辉三角 （C语言代码）

DNA （C语言代码）

计算质因子 （C语言代码）

良心推荐——>题解1049：C语言程序设计教程（第三版）课后习题11.1 （C语言描述——简单明了，时间复杂度低）

数字整除（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）如果a<0，那就不是这个代码了，哈哈哈哈

　　评论区

蓝桥杯历届试题-九宫重排（C++代码）

数对（C语言代码）

杨辉三角（C语言代码）

计算质因子（C语言代码）