本文主要是介绍PTA--球队“食物链”--《DS&A课程实践》第二次算法练习，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

球队食物链

• 一、 题目
• 二、题目分析
• 三、源代码

一、 题目

二、题目分析

1. 需要用图的数据结构，并且是有向图采用邻接表简单一些，邻接表可以自己实现，也可以用STL的map+vector实现，个人比较喜欢用vector数组实现，简单方便，但是题中的图可能出现重复的有向边，我们又不需要，并且最终我们要找字典序最小的环，则最开始就给边去重并且给边表序列从小到大排序，所以采用set容器（自动排序和去重）
2. 题目翻译一下就是在图中找一个包含了所有结点的有向环
3. 直接想法就是DFS，但是普通的dfs直接一次性遍历完所有结点最后返回到起始结点就结束了，不能保证每条路径都能搜索到，改造一下，往下深搜的时候将遍历的结点存储到结果数组中，并标记访问过，往上返回的时候又将遍历过的结点吐出来，就是从结果数组中删除，并且标记未访问，便于找经过该结点的另外一条路径
4. 往下的过程中，每到达一个结点就进行判断是否遍历完所有的结点了，并且结果数组的最后一个结点能到达起始结点，则该序列是满足要求的
5. 循环遍历所有的结点，将每一个结点都当做起始结点进入DFS，由于边表最开始就排好序了，所以找到符合条件的第一个环就可以结束了，return return return
6. 一开始想用stack来实现在序列尾部不断增加，删除，但是我需要在找到序列时遍历输出环，stack又不能单纯遍历，所以自己用数组模仿一下能遍历的栈容器
   结果超时了，有些细节没考虑到
   分析第四个测试点超时原因，对DFS进行剪枝
   特殊注意
   （1）我感觉，最开始先判断一下图连不连通，在源程序上直接改又感觉不够快，因为自造的DFS会找出所有的环，我只需要dfs一次就能判断是否连通，写个dfs
   （2）每次对剩下的没访问的结点进行判断一下，如果剩下的结点都没有能到达起始结点的边，那这个环肯定不行，回退

三、源代码

#include<bits/stdc++.h>
using namespace std;
#define MAXSIZE 22
set<int>G[MAXSIZE];
int n,now;
bool visited[MAXSIZE];
int ans[MAXSIZE]; 
bool f;    //标记结果环是否找到 
void dfs(int i)   //判断图是否连通的基本dfs 
{
	visited[i]=true;
	for(set<int>::iterator it=G[i].begin();it!=G[i].end();it++)
	{
		if(!visited[*it]) 
		{
			dfs(*it);	
		}
		
	}
}
void my_dfs(int i)
{
	if(f) return ;
	visited[i]=true;
	now++;
	ans[now]=i;  //把当前结点存到结果数组里面 
	if(now==n&&G[ans[now]].count(ans[1])) //遍历完所有的结点了，判断最后一个结点是否能到起始结点 
	{
		f=true;  //找到一个序列就标记输出，后面的都不用继续了 
		printf("%d",ans[1]);
		for(int i=2;i<=now;i++)
		{
			printf(" %d",ans[i]);
	 	}
		return ;
	}
	
	bool last=false;   //判断没有访问过的结点有没有能到达起始结点的 
	for(int j=1;j<=n;j++)
	{
		if(!visited[j]&&G[j].count(ans[1])) 
		{
			last=true;
			break;
		}
	}
	if(!last)  return ;
	
	for(set<int>::iterator it=G[i].begin();it!=G[i].end();it++)
	{
		int t=(*it);
		//cout<<t<<"  "<<endl;
		if(!visited[t]) 
		{
			my_dfs(t);
			visited[t]=false;  //dfs回退，将该结点从结果环中删除，找另外的环 
			now--;	
		}
		
	}
}

bool Find_List()
{
	for(int j=1;j<=n;j++)  visited[j]=false;
	dfs(1);  //先判断一下图是否连通 
	for(int j=1;j<=n;j++) 
	{
		if(!visited[j]) return false;//图根本不连通，直接就结束了
	}
	for(int i=1;i<=n;i++)   //从最小的结点开始找环，让每个结点都为起始结点 
	{
		for(int j=1;j<=n;j++)  visited[j]=false;
		now=0;
		my_dfs(i);
		if(f) return true;
	}
	return false;
}
int main()
{
	scanf("%d",&n);
	char c;
	f=false;
	for(int i=1;i<=n;i++)   //读入图到set中 
	{
		for(int j=1;j<=n;j++)
		{
			cin>>c;
			if(c=='W') G[i].insert(j);
			else if(c=='L')  G[j].insert(i);
		}
	}
	
	if(!Find_List())  printf("No Solution");
	return 0;
}
/*
5     //模拟一个不连通的图
-DDDD
D-DWL
DD-DW
DDW-D
DDDD-


*/

我这个说得有点啰嗦，可以参考下面这篇博客
https://blog.csdn.net/Morzker/article/details/102537956

1.写代码的时候模拟dfs的过程，想着怎么改进代码能到达想要的效果
2.想想办法对超时的dfs进行剪枝，有时候到达一个结点后没必要再递归下去了，递归是很费时的，对于特殊图（不连通）也可以单独处理
3.涉及序列最小时，都尽量在最开始就对结点排序，这样遍历过程中找到一个符合要求的即可直接输出并结束程序

这篇关于PTA--球队“食物链”--《DS&A课程实践》第二次算法练习的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！