Connected Components(连通分量)

题目链接：https://cn.vjudge.net/problem/Aizu-ALDS1_11_D

题目大意:通过输入的朋友关系，从指定人物出发通过双向朋友链是否能抵达目标人物；

归结为求图中各连通分量。用邻接表来存图。通过dfs或bfs遍历图,给各连通图的点分配不同的颜色以便于区分。下面以dfs为例。

代码如下:

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <stack> #include <vector> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int maxn=1e5+10; int t,n,m,x,v,a1,a2,g=1; vector<int> V[maxn]; int color[maxn]; void dfs(int u){//递归写法 color[u]=g; for(int i=0;i<V[u].size();i++){ if(!color[V[u][i]]) dfs(V[u][i]); } } void dfs_(int u){//非递归写法 color[u]=g; stack<int> s; s.push(u); while(!s.empty()){ int now=s.top();s.pop(); for(int i=0;i<V[now].size();i++){ int vv=V[now][i]; if(!color[vv]){ color[vv]=g; s.push(vv); } } } } int main() { cin>>n>>m; for(int i=0;i<m;i++){ cin>>x>>v; V[x].push_back(v);//由于是无向图，所以你懂 V[v].push_back(x); } /*for(int i=1;i<=n;i++){ cout<<i<<" "; for(int j=0;j<V[i].size();j++){ cout<<V[i][j]<<" "; } cout<<endl; }*/ for(int i=0;i<n;i++){ if(!color[i]){ //dfs(i); dfs_(i); g++; } } cin>>t; for(int i=1;i<=t;i++){ cin>>a1>>a2; if(color[a1]==color[a2])printf("yes\n"); else printf("no\n"); } return 0; }