链接就不给了,蓝桥杯试题集往年题 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.
Comments | 0 条评论