小黑

用户名：20190341315

访问量：8041

签　名：

菜！是真的菜，水题还做不全乎！菜。

等　　级
排　　名	126
经　　验	7720
参赛次数	8
文章发表	25
年　　龄	0
在职情况	学生
学　　校	郑州商学院
专　　业	计算机科学与技术

　　自我简介：

C/C++初学菜鸟

TA的其他文章

2447: 信息学奥赛一本通T1541-数列区间最大值
浏览：355

题目 2366: 信息学奥赛一本通T1456-图书管理 C++/Java
浏览：353

1737: 二叉搜索树 C++/Java
浏览：161

你可能喜欢

蓝桥杯算法提高VIP-卡勒沃夫之弱水路三千(提高型)(非拓扑排序,递归从无序到有序)

　　作者: 小黑　　　　发表时间：2020-11-17 18:54:29 浏览：351　|　评论：0　

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

### 这一题的主思路是:拓扑排序;不过这一题不必用拓扑排序;递归也可以;
#### 思路:
#### (1)先去重;
#### (2)根据已给顺序,循环比较,不符合已给的顺序的两个字符串交换次序;这样就有递归方向了,递归终止的条件：无重字符串集合符合题目给出的顺序;
## 更新于(2021/5/20)
## 思路：
## 拓扑排序(代码最下面)
```
#include<iostream>
#include<string.h>
using namespace std;
char s1[1010][110];
char s2[1010][110];
char str[1010][110];
void fun(int m,int k)
{
    for(int i=0;i<m;i++)//m对mm的名字，表示m对mm的先后顺序 
        {
            int x=0,y=0;
            for(int j=0;j<k;j++)//根据m对mm的先后顺序，来对k个mm的名字进行排序 
            {
                if(strcmp(str[j],s1[i])==0)//s1[i]mm先于s2[i]mm 
                x=j;
                if(strcmp(str[j],s2[i])==0)
                y=j;
            }
            if(x>y)//x>y说明s1[i]mm的名字在 s2mm的名字的后面；因此，两个mm的名字交换位次 
            {
                char t[11];
                strcpy(t,str[x]);
                strcpy(str[x],str[y]);
                strcpy(str[y],t);
            }
        }
        for(int i=0;i<m;i++)//重复上面的判断，直到次序正确 
        {
            int x=0,y=0;
            for(int j=0;j<k;j++)
            {
                if(strcmp(str[j],s1[i])==0)
                x=j;
                if(strcmp(str[j],s2[i])==0)
                y=j;
            }
            if(x>y)//x>y说明s1[i]mm的名字在 s2mm的名字的后面；说明位次还未排好
            fun(m,k);//继续调用函数排序
        }
}
int main()
{
    int n,m;
    scanf("%d",&n);//n组数据 
    while(n--)
    {
        
        int k=0;
        scanf("%d",&m);//m组mm名字 
        getchar();
        for(int i=0;i<m;i++)
        {
            scanf("%s%s",s1[i],s2[i]);//输入两个mm的名字，前一个先于后一个 
            strcpy(str[k],s1[i]);//将两个mm的名字全部合并到str中 
            k++;
            strcpy(str[k],s2[i]);//s1，s2数组并列记录两个mm顺序 
            k++;
            getchar();
        }
        for(int i=0;i<k-1;i++)//mm名字去重 
        for(int j=i+1;j<k;j++)
        {
            if(strcmp(str[i],str[j])==0)
            {
                for(int a=j;a<k;a++)
                strcpy(str[a],str[a+1]);
                k--;
                j--;
            }
        }//m对mm名字；k：不重复的mm名字 
        fun(m,k);//调用函数，mm按先后排序（深搜） 
        for(int i=0;i<k;i++)//输出mm 
        if(i==k-1)
        printf("%s\n",str[i]);
        else
        printf("%s ",str[i]);
    }
    return 0;
}
```
## 拓扑排序
```javascript
#include<iostream>
#include<map>
#include<vector>
#include<stack>
using namespace std;
map<string,vector<string> >e;//邻接表 (vector储存表头指向的结点)
map<string,int> in;//结点入度 
stack<string>s; //栈(string) 
int main() 
{
	int n,num;
	string s1,s2,t,x;
	cin>>num;
	while(num--) 
	{
		cin>>n;//输入边数 
		for(int i=0; i<n; i++) 
		{
			cin>>s1>>s2;//输入有向边s1->s2 
			e[s1].push_back(s2);//逻辑构造s1->s2有向边 
			in[s2]++;//每个结点的入度记录 
			if(in.count(s1) == 0) 
			{//生成拓扑序的第一个结点 
				in[s1]=0;
			}
		}
		vector<string>::iterator i;
		map<string,int>::iterator it;
		for(it=in.begin(); it!=in.end(); it++)//在入度表中查询入度为0的结点 
			if(it->second==0)//寻找入度为0的结点 
				s.push(it->first);//首个入栈 
		while(s.size()) 
		{
			t=s.top();//访问栈顶元素 
			cout<<t<<" ";//出栈输出 
			s.pop();//出栈 
			//遍历t指向的结点 
			for(i=e[t].begin(); i!=e[t].end(); i++) 
			{
				x=*i;
				in[x]--;//入度-1等价于断开t->x这条有向边 
				if(in[x]==0)//入度为0 
					s.push(x);//入栈 
			}
		}
		cout<<endl;
		in.clear();//清空map容器(防止干扰下次操作) 
		e.clear();
	}
	return 0;
}
```

0.0分

4 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

小黑

TA的其他文章

你可能喜欢

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

【明明的随机数】（C语言代码）

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

C二级辅导-统计字符（C语言代码）

数组输出（C语言代码）

蓝桥杯算法提高VIP-卡勒沃夫之弱水路三千(提高型)(非拓扑排序,递归从无序到有序)

评论区

精彩推荐

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

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

本人酷爱递归实现很多问题，这里也是

文科生的悲哀（C语言代码）

模拟计算器（C语言代码）

矩阵转置（C语言代码）

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

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

蛇行矩阵（Java代码）

Manchester- A+B for Input-Output Practice (V)

小黑

TA的其他文章

你可能喜欢

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

【明明的随机数】 （C语言代码）

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

C二级辅导-统计字符 （C语言代码）

数组输出 （C语言代码）

蓝桥杯算法提高VIP-卡勒沃夫之弱水路三千(提高型)(非拓扑排序,递归从无序到有序)

评论区

精彩推荐

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

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

本人酷爱递归实现很多问题，这里也是

文科生的悲哀 （C语言代码）

模拟计算器 （C语言代码）

矩阵转置 （C语言代码）

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

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

蛇行矩阵 （Java代码）

Manchester- A+B for Input-Output Practice (V)

【明明的随机数】（C语言代码）

C二级辅导-统计字符（C语言代码）

数组输出（C语言代码）

　　评论区

文科生的悲哀（C语言代码）

模拟计算器（C语言代码）

矩阵转置（C语言代码）

蛇行矩阵（Java代码）