Advertisement
jakaria_hossain

Disjoint Set

Mar 12th, 2019
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.70 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. void makeset(int n, int ara[])
  4. {
  5. ara[n]=n;
  6. }
  7. int findr(int x,int ara[])
  8. {
  9. if(ara[x]==x)return x;
  10. return findr(ara[x],ara);
  11. }
  12. void dounion(int a, int b, int ara[])
  13. {
  14. int x= findr(a,ara);
  15. int y = findr(b, ara);
  16. if(x==y)return;
  17. else ara[x]=y;
  18. }
  19. int main()
  20. {
  21. int node, edge;
  22. cin>>node>>edge;
  23. int ara[node+1];
  24. int u,v;
  25. for(int i=0;i<edge;i++)
  26. {
  27. cin>>u>>v;
  28. makeset(u,ara);
  29. makeset(v,ara);
  30. dounion(u,v,ara);
  31. }
  32. int x, y;
  33. cin>>x>>y;
  34. int p,q;
  35. p=findr(x,ara);
  36. q=findr(y,ara);
  37. if(p==q)cout<<"yes"<<endl;
  38. else cout<<"no"<<endl;
  39. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement