试题 历届试题 发现环 dfs解法(无超时)

资源限制
时间限制:1.0s 内存限制:256.0MB
问题描述
  小明的实验室有N台电脑,编号1~N。原本这N台电脑之间有N-1条数据链接相连,恰好构成一个树形网络。在树形网络上,任意两台电脑之间有唯一的路径相连。

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

为了恢复正常传输。小明需要找到所有在环路上的电脑,你能帮助他吗?
输入格式
  第一行包含一个整数N。
  以下N行每行两个整数a和b,表示a和b之间有一条数据链接相连。

对于30%的数据,1 <= N <= 1000
  对于100%的数据, 1 <= N <= 100000, 1 <= a, b <= N

输入保证合法。
输出格式
  按从小到大的顺序输出在环路上的电脑的编号,中间由一个空格分隔。
样例输入
5
1 2
3 1
2 4
2 5
5 3
样例输出
1 2 3 5
/-------------------------------------------------------------------------------------------------------/

参考博客点此

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<vector> 
#include<cstring>
using namespace std;
const int maxn = 100005; 
struct node{
	int end;//终点的序号
	int vis;//是否被访问过
};
int road[maxn];//记录经过的路径
vector<node> roads[maxn];//定义一个结构体数组记录节点之间的联系,有很多条联系所以road加了s。。。以下代码注意区分
int vis[maxn];//记录路径是否经过该节点,经过一次后则为非原始定义值,当第二次到达该节点时,值为非原始定义值,就是环路产生
int huan[maxn];//最终环的路径
int r;//数组road【】的下标
int h;//数组huan【】的下标
void dfs(int x){
	if(vis[x] != -1){//第二次到达x节点,代表环路形成,记录最终环路径,结束dfs
		for(int j = vis[x];j < r;j++){
			huan[h++] = road[j];
		}
		return ;
	}
	vis[x] = r;
	road[r] = x;
	r++;
	for(int i=0;i<roads[x].size();i++){
		if(roads[x][i].vis!=true){
			roads[x][i].vis = true;
			int z = roads[x][i].end;
			for(int j=0;j<roads[z].size();j++){//切断两节点之间的联系,防止返回造成环路假象
				if(roads[z][j].end == x){
					roads[z][j].vis = true;
					break;
				}
			}
			dfs(z);
			r--;
		}
	}
	return ;
}

int main(){
	int a,b,n;
	cin>>n;
	for(int i=0;i<n;i++){//录入各个节点的链接
		cin>>a>>b;
		node temp;
		temp.end = b;temp.vis = false;
		roads[a].push_back(temp);
		temp.end = a;
		roads[b].push_back(temp);
	}
	memset(vis,-1,sizeof(vis));//将vis原始值定义为-1
	dfs(1);
	sort(huan,huan+h);//排序
	for(int i=0;i<h;i++)//输出环路
		cout<<huan[i]<<" ";
	return 0;
}
上一篇:敏捷转型行动笔记:内部敏捷教练实践


下一篇:[POI2008] CLO