藍橋杯：曆屆試題 發現環（并查集 + DFS）

問題描述

　　小明的實驗室有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

鳴謝：https://blog.csdn.net/qq_41608020/article/details/80329348#commentBox

這位部落客思路講得很清晰，代碼寫的也很簡潔

【思路】

我想總結的就是，首先一定要認真審題。這題我剛開始做的時候，題一掃就過了，沒發現它的條件。這題說有n個節點，但是隻有n條邊。由離散數學知識我們知道，n個結點如果有n - 1條邊，那麼這個圖就是一個樹。然而此題，它有n條邊，說明這個樹種存在且僅存在一個環！是以，不需要考慮多個環的情況！

是以，我們采用了并查集幫助我們。每行輸入兩個節點，表示它們有一條邊相連，如果兩個節點之前不屬于同一個子網（即boss節點不相同），那麼我們就把它們merge起來，變成同一個子網。 如果這兩個節點已經屬于同一個子網了，又來了一條邊相連，那麼此時我們就可以說，這兩個點一定在環上了！ 畫個圖其實很好分析。這個過程我們借助并查集可以很友善的做出來！

由于隻存在一個環，然後此時我們也找到這個環上存在的兩個點了，那麼一個作為起點S，一個作為終點E，開始dfs搜就可以了。 因為環已經存在了，且隻有一個環，是以後面輸入什麼邊跟我已經沒有關系了，此時直接開始搜，一定可以把環上的所有點都周遊到 。這個過程就是一個簡單的dfs了。

存儲圖之間的關系，我們用類似領接表的資料結構

vector<int> v[200010];

這個資料結構在圖的題目中非常好用，可以處理很多大資料的問題。另外有個坑點就是，getBoss函數，如果不寫成三元運算符的形式

return parent[x] == x ? x : parent[x] = getBoss(parent[x]);

居然就會逾時！！！這我很不明白藍橋杯的評測系統了。。。。

AC代碼：

/*
由題，因為n個節點隻有n條邊，是以圖中一定隻可能有一個環，是以我之前考慮了多個環的情況
多慮了 
是以，用一個f變量來做标記，一旦找到在環上的兩個點，那麼就沒有必要再用并查集判斷了
直接一個作為起點S一個作為終點E，進行dfs找路徑就可以了！ 
*/ 
#include<iostream>
#include<vector>
using namespace std;

const int maxn = 100005;
int book[maxn];
int n, S, E, f = 0;
int parent[maxn];
vector<int> v[200010];
bool flag = false;

void init()
{
	for(int i = 0;i < maxn;i++)
		parent[i] = i;
}

int getBoss(int x)
{
	return parent[x] == x ? x : parent[x] = getBoss(parent[x]);
}

void dfs(int k)
{
	if(flag)
		return ;
	if(k == E)						//如果搜到終點 
	{
		for(int i = 1;i <= n;i++)	//滿足從小到大的周遊輸出 
		{
			if(book[i] == 1)
			{
				if(f == 0)			//控制輸出的一個變量而已 
				{
					f = 1;
					cout << i;
				}
				else
				{
					cout << " ";
					cout << i;	
				}
			}
		}
		flag = true;
		return ;
	}
	
	//枚舉k節點能到達的所有結點 
	for(int i = 0;i < v[k].size();i++)
	{
		int next = v[k][i];			//下一個要搜的節點
		if(book[next] != 1)
		{
			book[next] = 1;
			dfs(next);
			if(flag)
				return ;
			book[next] = 0;
		} 
	}
}

int main()
{
	int a, b, f = 1;		//f相當于一個标記變量 
	cin >> n;				//邊的條數				
	init();
	//輸入邊資訊 
	for(int i = 0;i < n;i++)
	{
		cin >> a >> b;
		if(f == 1)			 
		{
			int q = getBoss(a);
			int w = getBoss(b);
			if(q != w)				//如果兩者不在同一個子網中 
			{
				v[a].push_back(b);
				v[b].push_back(a);
				parent[q] = w;		//q和w放到一個子網中了 
			}
			else					//如果兩者在同一個子網中了，現在又有一條邊把他們串起來 
			{					//那說明，這兩個點肯定在環上面！ 
				S = a;			//等會兒dfs的起點S 
				E = b;			//等會兒dfs的終點E 
				f = 0;			//沒有必要再用并查集繼續判斷，已經找到了環上的兩個點！ 
			}
		}
	}
	book[S] = 1;				//起點标記一下，表示走過
	dfs(S);						//從起點開始搜 
	return 0;
}
           

這題主要是思路難想了，借助了并查集。是一道好題！