試題 曆屆試題 發現環 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;
}