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

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


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


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

思路

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

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

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

范例

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

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

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

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

到这里，思路已经十分清晰了，但是我总觉得我这题写复杂了，感觉蛮简单一题的，但是我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.