連通分量 | Connected Components | C/C++實作

問題描述

請編寫一個程式，輸入SNS的朋友關系，判斷從指定人物出發能否通過雙向朋友鍊抵達人物。

輸入： 第1行輸入代表SNS使用者數的整數n以及代表朋友關系數的m，用空格隔開。SNS各使用者的ID分别為0到n-1。

接下來的m行輸入朋友關系，每個朋友關系占1行。1個朋友關系包含s、t這兩個整數，表示s和t為朋友。s、t輸入時用空格隔開。

緊接下來的1行輸入問題數q。再接下來的q行輸入問題。

各問題均為用空格隔開的2個整數s、t，表示從s出發能否抵達t？

輸出： 如果從s出發能抵達t就輸出yes，否則輸出no，每個問題的回答占1行。

限制：

2 ≤ n ≤ 100000

0 ≤ m ≤ 100000

1 ≤ q ≤ 10000

輸入示例

10 9
0 1
0 2
3 4
5 7
5 6
6 7
6 8
7 8
8 9
3
0 1
5 9
1 3
           

輸出示例

yes
yes
no
           

講解

這是一個求圖連通分量(Connected Components)的問題。對于一個連通性未知的圖G，其極大聯通子圖即為G的連通分量。在G的連通子圖中，如果包含G’的圖隻有G’，那麼G’就是G的極大連通子圖。

連通分量可以通過深度優先搜尋和廣度優先搜尋來尋找。在本題中，我們需要對頂點數和邊數都很多的大規模圖進行深度優先或廣度優先搜尋，是以不能采用消耗記憶體空間為O(n^2)的鄰接矩陣。于是我們用鄰接表來表示圖。

鄰接表适合邊數較少的稀疏圖。在無權值有向圖的鄰接表中，各項點都對應着一個相鄰頂點的編号清單。如果換作無向圖，那麼隻要u的清單中包含v，v的清單中也就一定包含u。

vector<int> G[100];//表示有100個頂點的圖的鄰接表
......................................
G[u].push_back(u);//從頂點u向頂點v畫邊
................................................
//搜尋與頂點u相鄰的頂點v
for(int i = 0; i < G[u].size(); i++){
	int v = G[u][i];
	....................
}
           

求圖的連通分量時，需要以未通路的頂點為起點循環執行深度優先搜尋（或廣度優先搜尋）。隻要在此過程中給每輪搜尋到的頂點配置設定不同的編号（顔色），我們就可以用O(1)來判斷指定的兩個頂點是否屬于同一組（顔色）了。

使用鄰接表的深度優先搜尋和廣度優先搜尋都需要對每個頂點各通路一次，同時還需對鄰接表中的頂點（邊）也逐一進行通路，是以算法複雜度為O(|V|+|E|)。

鄰接表表示法的優點：

隻需與邊數成正比的記憶體空間。

鄰接表表示法的缺點：

需要消耗O(n)來搜尋鄰接表。不過大部分算法（如BFS、DFS等）隻需對特定頂點的相鄰頂點進行一次周遊即可滿足需求，是以影響并不大。

難以有效删除邊。

AC代碼如下

#include<iostream>
#include<vector>
#include<stack>
using namespace std;
static const int MAX = 100000;
static const int NIL = -1;

int n;
vector<int> G[MAX];
int color[MAX];

void dfs(int r, int c){
	stack<int> S;
	S.push(r);
	color[r] = c;
	while( !S.empty() ){
		int u = S.top(); S.pop();
		for(int i = 0; i < G[u].size(); i++){
			int v = G[u][i];
			if(color[v] == NIL) {
				color[v] = c;
				S.push(v);
			} 
		}
	}
} 

void assignColor(){
	int id = 1;
	for(int i = 0; i < n; i++) color[i] = NIL;
	for(int u = 0; u < n; u++){
		if(color[u] == NIL) dfs(u, id++);
	}
}

int main(){
	int s, t, m, q;
	
	cin>>n>>m;
	
	for(int i = 0; i < m; i++){
		cin>>s>>t;
		G[s].push_back(t);
		G[t].push_back(s);
	}
	
	assignColor();
	
	cin>>q;
	
	for(int i = 0; i < q; i++){
		cin>>s>>t;
		if(color[s] == color[t]){
			cout<<"yes"<<endl;
		} else {
			cout<<"no"<<endl;
		}
	}
	
	return 0;
}