鏈接：https://vjudge.net/problem/Aizu-ALDS1_11_D
本題求連通分量：即判斷兩個(gè)點(diǎn)之間是否有路徑际乘。
思路：用深度或者廣度進(jìn)行搜索，并用一個(gè)color數(shù)組對頂點(diǎn)就行標(biāo)記病梢，能連通的設(shè)置為同一個(gè)值，最后對數(shù)組進(jìn)行查詢即可。本題用vector代替鏈表實(shí)現(xiàn)鄰接表。
代碼：（dfs版本）
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
int n;
vector<int> G[100000];
int color[100000];
void dfs(int r,int c){
stack<int> S; //開棧進(jìn)行深度優(yōu)先搜索
S.push(r);
color[r] = c; //標(biāo)記顏色
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]==-1){ //若未訪問過則入棧
color[v] = c;
S.push(v);
}
}
}
}
void setcolor(){
int id = 1;
for(int i=0;i<n;i++)color[i] = -1; //初始化color數(shù)組
for(int i=0;i<n;i++){
if(color[i]==-1)dfs(i,id++); //對每個(gè)頂點(diǎn)進(jìn)行搜索
}
}
int main(){
int a,b,c,d;
cin>>n>>a;
while(a--){
cin>>b>>c;
G[b].push_back(c);
G[c].push_back(b);
}
setcolor();
cin>>d;
while(d--){
cin>>b>>c;
if(color[b]==color[c])
cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
return 0;
}
代碼：（bfs版本）：
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n;
vector<int> G[10000];
int color[10000];
void bfs(int r,int c){
queue<int> S;
S.push(r);
color[r] = c;
while(!S.empty()){
int u = S.front();
S.pop();
for(int i=0;i<G[u].size();i++){
int v = G[u][i];
if(color[v]==-1){
color[v] = c;
S.push(v);
}
}
}
}
void setcolor(){
int id = 1;
for(int i=0;i<n;i++)color[i] = -1;
for(int i=0;i<n;i++){
if(color[i]==-1)bfs(i,id++);
}
}
int main(){
int a,b,c,d;
cin>>n>>a;
while(a--){
cin>>b>>c;
G[b].push_back(c);
G[c].push_back(b);
}
setcolor();
cin>>d;
while(d--){
cin>>b>>c;
if(color[b]==color[c])
cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
return 0;
}
