【算法狂想曲】蓝桥杯 历届试题 发现环

2020-04-23   118 次阅读


链接就不给了,蓝桥杯试题集往年题 PREV-49

小明的实验室有N台电脑,编号1~N。原本这N台电脑之间有N-1条数据链接相连,恰好构成一个树形网络。在树形网络上,任意两台电脑之间有唯一的路径相连。


  不过在最近一次维护网络时,管理员误操作使得某两台电脑之间增加了一条数据链接,于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径,使得这些电脑上的数据传输出现了BUG。


  为了恢复正常传输。小明需要找到所有在环路上的电脑,你能帮助他吗?

思路

如何在图中寻找环路?
这题的题意预计是只有一个环,所以我们只需要寻找一次,而且默认是有且仅有一个环路

一开始的基本思路是使用回溯配合已访问标志来进行遍历
在当前走过的节点上都设置为已访问
如果在遍历的过程中遍历到已访问节点,说明这是一个环(从起点到终点都是同一点)
现在的问题是题目要求

  • 如何确定环路路径的起点(路径存储于数组中)
  • 因为链路是双向的,如何确保访问时不往回遍历
  • 如何从小到大输出(sort快排)

范例

给定一个如图中所示的网络,可以看到3,4,5,6,7构成了环
如果按照顺序输入,构造的邻接表如图所示(图有错误,3的邻接表应该是{2,4,7})
捕获.PNG

然而一旦输入顺序不定,就可能造成邻接表顺序混乱,特定下标位置不是它所对应的那个节点的邻接表,比如,在上图中,下标为2的位置对应的是节点2的邻接表,而在当前表中则为7
2.PNG

因此只需要再构造一个map来存储各个节点位于vector中的位置即可

3.PNG

随后就是确定目标路径的起点,其实也很简单,用一个数组用语来存储路径中各个节点的位置即可,一旦发现重复节点,直接可以将该节点作为下标找出目标路径起点

到这里,思路已经十分清晰了,但是我总觉得我这题写复杂了,感觉蛮简单一题的,但是我vector,map,快排都用上了,百分之99还有更好的方法
但是写出来还是很开心的,哈哈

AC代码

#include <iostream>
#include<string>
#include<math.h>
#include<string.h> 
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
//int connect[10001][10001];      //第一版代码中的愚蠢巨大二维数组
map<int,int> detect;  		  //用于存储各个节点处于vector中的位置
vector<vector<int> > connect;     //作为邻接表,存储各个节点的邻接节点
int path[100001];		 //存储路径
int pos[100001];		// 存储节点位于路径中的位置(方便寻找重复节点位置)
int pNum=0;			//路径长度
int whether[100001];		//访问标志,判断该节点是否被访问过
bool success = false;
int cmp(int a,int b)
{
	return a<b;
}

//回溯函数用于遍历
void backTrace(int current,int pre)
{
	int cur = detect[current];     //当前节点与当前节点所处vector位置是有区别的
	//倘若成功找到环,所有函数直接结束
	if(success)
	return;
	//倘若当前已访问标志为2(可优化,之前第一版代码中从bool改成了int,可改回bool,没时间改),说明环路已找到
	if(whether[current]==2)
	{
		 //可优化片段:因为不清楚如何用快排对数组中特定片段进行排序于是用了土方法,将整个目标路径移动到数组头并对头部局部排序
	for(int i=pos[current];i<pNum;i++)
	{
	path[i-pos[current]]=path[i];
	}

  
  	int pos1 = pNum-pos[current];
	sort(path,path+pos1,cmp);   //快速排序
	//输出结果
	for(int i=0;i<pNum-pos[current];i++)
	{
	std::cout<<path[i]<<" ";
	}
		std::cout<<std::endl;
		
		success = true;
		return;
	}
	//将当前节点压入路径中(因为无法确定当前节点是否处于环路中,先压入,如果不在环路中后期回溯会将该元素弹出)
	pos[current]=pNum;
	path[pNum++]=current;
	//对当前节点的所有邻接节点(除了来者节点)进行遍历
	for(int i=0;i<connect[detect[current]].size();i++)
	{
		whether[current]=2;   //设置标志
	//滤掉来者节点防止无边死循环(反复横跳)
	    if(connect[detect[current]][i]!=pre)
		{
		backTrace(connect[detect[current]][i],current);	
		pNum--;
	}
	}
}
int main(int argc, char** argv) {
	
	int N;
	std::cin>>N;
	for(int i=0;i<N;i++)
	{
		int temp1,temp2;
		std::cin>>temp1>>temp2;
		//将两个节点分别进行邻接表的添加
		//如果当前节点不存在于vector中,将其添加入其中
		if(detect.find(temp1)!=detect.end())
		{
			connect[detect[temp1]].push_back(temp2);
	
		}
			
		else{
			detect[temp1]=connect.size();
				vector<int> temp;
				temp.push_back(temp2); 
			connect.push_back(temp);
		}
			if(detect.find(temp2)!=detect.end())
		{
			connect[detect[temp2]].push_back(temp1);
		}
			
		else{
			detect[temp2]=connect.size();
			vector<int> temp;
				temp.push_back(temp1); 
			connect.push_back(temp);
		}
		
		
		//connect[temp1][++connect[temp1][0]]=temp2;
		//connect[temp2][++connect[temp2][0]]=temp1;
	}
	//依次回溯
	for(int i=0;i<N;i++)
	{
		
	backTrace(1,0);
	if(success)
	break;
	
}

	return 0;
}

/*
10 5
1 4 2 8 5 7 1 4 2 8


1 3 4 5 6 7 8 9 10 11
*/


Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议