问题标题: 酷町堂：2075 庞大的家族 1

2075   庞大的家族 1

题目描述 Description

家族关系很复杂，两个离得很远的人可能是亲戚，两个日常生活中的好朋友也可能有亲戚关系。如果有完整的家谱，那就算地理位置再远我们也可以正确判断两个人是否有亲戚关系。

如果家谱十分庞大，可能存在两个有亲戚关系的人的最近公共祖先与他们相隔多代，那么检验亲戚关系并非人力能及。此时我们可以通过计算机来帮我们来计算。

为了简化关系，你将有一些亲戚关系的信息，如A和B是亲戚，B和C是亲戚等。从这些信息中可以推算出A和C是亲戚等。请你写一个程序，对于我们关于亲戚关系的提问，以最快的速度给出答案。

输入描述 Input Description

输入由两部分组成。
第一部分以N，M开始。N为问题涉及的人的个数( 1 ≤ N ≤ 20000)。这些人的编号为1,2,3,…, N。下面有M行( 1 ≤ M ≤ 1 000 000 )，每行有两个数ai, bi，表示已知ai和bi是亲戚。
第二部分以Q开始。以下Q行有Q个询问( 1 ≤ Q ≤ 1 000 000 )，每行为ci, di，表示询问ci和di是否为亲戚。

输出描述 Output Description

对于每个询问ci, di，输出一行：若ci和di为亲戚，则输出“Yes”，否则输出“No”。

样例输入 Sample Input

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

样例输出 Sample Output

Yes
No
Yes

#include <iostream>
using namespace std;
const int MAXN=20005;
int fa[MAXN],n,m,q;
void init() {
    for(int i=1;i<=n;i++)
        fa[i]=i;
} 
int find(int x) {
    if(x==fa[x])    return x;
    return fa[x]=find(fa[x]);
}
void unite(int x, int y) {
    x=find(x);
    y=find(y);
    fa[y]=x;
}
bool same(int x, int y) {
    return find(x)==find(y);
}
int main() {
    cin>>n>>m;
    init(); 
    for(int i=1;i<=m;i++) {
        int x,y;
        cin >>x>>y;
        unite(x,y);
    }
    cin>>q;
    for(int i=1;i<=q;i++) {
        int x, y;
        cin >> x >> y;
        if(same(x, y))  cout<<"Yes"<<endl;
        else    cout<<"No"<<endl;
    }
    return 0;
}

为什么90！！