并查集入门题
Input
第一行输入N(1 ≤ N ≤ 5000),M(1 ≤ M ≤ 5000),Q(1 ≤ Q ≤ 5000),分别表示人数,关系数,询问次数。
接着输入M行,每行两个整数a,b,表示a和b之间有亲戚关系。
接着输入Q行,每行两个整数a,b,表示询问a和b之间是否有亲戚关系。
Output
为每条询问输入一行,当有亲戚关系时,输出yes,否则输出no.
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int MAX = 5120; int f[MAX]; int findset(int x) { if (x==f[x]) return x; f[x]=findset(f[x]); return f[x]; } void unionset(int x,int y) //合并,时间复杂度最坏是O(n) { int fx=findset(x); int fy=findset(y); if(fx!=fy) f[fx]=fy; } int main() { int n,m,q; int x,y; while(scanf("%d%d%d",&n,&m,&q)==3) { int i; for(i=1;i<=n;i++) { f[i]=i; } while(m--) { scanf("%d%d",&x,&y); unionset(x,y); } while(q--) { scanf("%d%d",&x,&y); if(findset(x)==findset(y))printf("yes\n"); else printf("no\n"); } } return 0; }