描述
编写一个程序,读取 SNS(社交网络服务)中的关系,并判断给定的用户对是否可以通过网络相互访问。
输入
第一行给出了两个整数n和m。n 是 SNS 中的用户数,m 是 SNS 中的关系数。SNS 中的用户由 ID 0,1,...,n-1 标识。
在接下来的 m 行中,给出了关系。每个关系由两个整数 s 和 t 给出,表示 s 和 t 是朋友(并且彼此可达)。
在下一行中,给出了查询的数量 q。在接下来的q行中,分别给出了q个查询。每个查询由两个整数 s 和 t 组成,由空格字符分隔。
2≤n≤100,000
0≤m≤100,000
1≤q≤10,000
输出
对于每个查询,如果 t 可以通过社交网络从 s 到达,则打印“yes”,否则打印“no”。
样例输入
10 9
0 1
0 2
3 4
5 7
5 6
6 7
6 8
7 8
8 9
3
0 1
5 9
1 3
样例输出
yes
yes
no
题意:有n个点m条边,q次询问,对m条边并查集后q次询问x,y是否连通
#include<bits/stdc++.h> using namespace std; const int N = 1e5+10; int f[N],a[N]; int n,m,q; int find(int x) { if(f[x]!=x)f[x] = find(f[x]); return f[x]; } void merger(int x,int y) { int fx = find(x); int fy = find(y); f[fx] = fy; a[fy]+=a[fx]; } int main() { cin>>n>>m; for(int i=0;i<=n;i++)f[i] = i; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; if(find(x)!=find(y))merger(x,y); } cin>>q; for(int i=1;i<=q;i++) { int x,y; cin>>x>>y; if(find(x)!=find(y))cout<<"no"<<endl; else cout<<"yes"<<endl; } return 0; }