题目链接：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_D
给一些Social Network中的好友关系，然后求两者是不是好友（通过好友的好友也算是好友）比如1和2是好友，2和3是好友，那么1和3也算是好友
思路：把每个人看作是一个节点，每个好友关系看做是一条边，是好友关系就表示二者是在同一个连通分量里，连通分量用color来标识，两个节点的color值相等就标识这二者是在同一连通分量的。
具体代码如下：
#include <cstdio> #include <iostream> #include <algorithm> #include <queue> #include <stack> #include <vector> using namespace std; const int maxx=100100; vector<int> A[maxx]; int color[maxx]; int c=1; void dfs(int u){ if(color[u]!=-1) return ;//当该节点已经属于某一联通分量时，不需要染色 color[u]=c; int si=A[u].size(); for(int i=0;i<si;i++){ if(color[A[u][i]]==-1){//注意是对A[u][i]进行染色 dfs(A[u][i]); } } return ; } int main(){ int n,q,a,b; cin>>n>>q; for(int i=0;i<maxx;i++) color[i]=-1; for(int i=1;i<=q;i++){ cin>>a>>b; A[a].push_back(b); A[b].push_back(a); } for(int i=0;i<n;i++){ dfs(i); c++; } cin>>q; for(int i=1;i<=q;i++){ cin>>a>>b; if(color[a]==color[b]) cout<<"yes"<<endl; else cout<<"no"<<endl; } return 0; }错点：
1.要在dfs最开始加上对if(color[u]!=-1) return ;这个的判断
2.遍历邻接表的时候，不需要遍历所有节点了，只要遍历这个节点后面的链表（向量）就可以了。
3.遇到的问题是：n的定义只能放在main函数里，放在全局里会在进行完染色操作后使n变为-1。
后来发现原因是，在写color数组初始化的时候，把结尾写成了<=maxx，应该是<maxx，导致在全局申请n的时候，申请了和color的末尾+1元素重合的内存，导致对n也进行了赋值-1的操作，导致n出现了问题。感谢 @toptp2017 大佬的帮助！
-------------------------2018.6.23更新----------------------------------------------------
之前写的时候是用连通分量dfs染色来写的，也可以使用并查集写的更快；
读入过程就看做 union的过程，判断过程就是判断两个元素是否在同一集合内的same的过程；
关于并查集具体在这个blog里：https://blog.csdn.net/qq_33982232/article/details/80718042
代码如下：
#include <cstdio> #include <iostream> #include <algorithm> #include <vector> using namespace std; const int maxx=100010; int pre[maxx]; int find(int u){ if(pre[u]!=u) pre[u]=find(pre[u]); return pre[u]; } int main(){ int n,m,x,y; cin>>n>>m; for(int i=0;i<n;i++) pre[i]=i; while(m--){ cin>>x>>y; pre[find(x)]=find(y); } cin>>m; while(m--){ cin>>x>>y; if(find(x)==find(y)) cout<<"yes"<<endl; else cout<<"no"<<endl; } return 0; }错点：
1.find函数判断是if不是while
