AOJ Connected Components(连通分量)

链接：https://vjudge.net/problem/Aizu-ALDS1_11_D
本题求连通分量：即判断两个点之间是否有路径。

思路：用深度或者广度进行搜索，并用一个color数组对顶点就行标记，能连通的设置为同一个值，最后对数组进行查询即可。本题用vector代替链表实现邻接表。

代码：（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; //开栈进行深度优先搜索
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]==-1){ //若未访问过则入栈
color[v] = c;
S.push(v);
}
}
}
}

void setcolor(){
int id = 1;
for(int i=0;i<n;i++)color[i] = -1; //初始化color数组
for(int i=0;i<n;i++){
if(color[i]==-1)dfs(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;
}

代码：（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;
}