Advertisement
Guest User

Untitled

a guest
Feb 24th, 2020
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.83 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int parent[100001],rnk[100001];
  4. int root(int u){
  5. if(parent[u]==u) return u;
  6. return parent[u]=root(parent[u]);
  7. }
  8. void mrg(int u,int v){
  9. u=root(u);
  10. v=root(v);
  11. if(u==v) return ;
  12. if(rnk[u]>rnk[v]){
  13. rnk[u]+=rnk[v];
  14. parent[v]=u;
  15. }
  16. else{//rnk[v]>rnk[u]
  17. rnk[v]+=rnk[u];
  18. parent[u]=v;
  19. }
  20. }
  21. int main(){
  22.  
  23. int n,q,k;
  24. scanf("%d %d %d",&n,&k,&q);
  25. for(int i=1;i<=n;i++){
  26. parent[i]=i;
  27. rnk[i]=1;
  28. }
  29. for(int i=0;i<k;i++){
  30. int u,v;
  31. scanf("%d %d",&u,&v);
  32. mrg(u,v);
  33. }
  34. for(int i=0;i<q;i++){
  35. int u,v;
  36. scanf("%d %d",&u,&v);
  37. if(root(u)==root(v)) printf("yes");
  38. else printf("no");
  39. printf("\n");
  40. }
  41. return 0;
  42. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement