球队食物链
一、 题目
二、题目分析
- 需要用图的数据结构,并且是有向图采用邻接表简单一些,邻接表可以自己实现,也可以用STL的map+vector实现,个人比较喜欢用vector数组实现,简单方便,但是题中的图可能出现重复的有向边,我们又不需要,并且最终我们要找字典序最小的环,则最开始就给边去重并且给边表序列从小到大排序,所以采用set容器(自动排序和去重)
- 题目翻译一下就是在图中找一个包含了所有结点的有向环
- 直接想法就是DFS,但是普通的dfs直接一次性遍历完所有结点最后返回到起始结点就结束了,不能保证每条路径都能搜索到,改造一下,往下深搜的时候将遍历的结点存储到结果数组中,并标记访问过,往上返回的时候又将遍历过的结点吐出来,就是从结果数组中删除,并且标记未访问,便于找经过该结点的另外一条路径
- 往下的过程中,每到达一个结点就进行判断是否遍历完所有的结点了,并且结果数组的最后一个结点能到达起始结点,则该序列是满足要求的
- 循环遍历所有的结点,将每一个结点都当做起始结点进入DFS,由于边表最开始就排好序了,所以找到符合条件的第一个环就可以结束了,return return return
- 一开始想用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.涉及序列最小时,都尽量在最开始就对结点排序,这样遍历过程中找到一个符合要求的即可直接输出并结束程序