AcWing
1249. 亲戚
两个优化策略：路径压缩(必须)、按秩合并(可选，一般不用)。
这题用cin、cout会超时。cin、cout的加速：
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
此外，用\n代替endl. 使用这种方法，不能再用scanf()、printf()、getchar()等，puts()可以用。
如果不用这种方法，就用scanf("%d%d", &n, &m);、printf("a=%d, b=%d", a, b)、puts(a)等。
#include <bits/stdc++.h>
using namespace std;
int n, m, q;
int myfather[20010], r[20010];
int getanc(int a){ // 路径压缩！！
if(myfather[a] != a) myfather[a] = getanc(myfather[a]);
return myfather[a];
}
void unions(int a, int b){ // 按秩合并，可以用常规的
// 常规：myfather[getanc(a)] = getanc(b);
int aa = getanc(a);
int bb = getanc(b);
if(r[aa] == r[bb]){
r[aa]++;
myfather[bb] = aa;
}
else if(r[aa] < r[bb]) myfather[aa] = bb;
else myfather[bb] = aa;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
for(int i = 0; i <= n - 1; i++) myfather[i] = i;
for(int i = 0; i <= m - 1; i++){
int a, b;
cin >> a >> b;
unions(a, b);
}
cin >> q;
while(q--){
int a, b;
cin >> a >> b;
if(getanc(a) == getanc(b)) cout << "Yes\n";
else cout << "No\n";
}
return 0;
}