SHARE
TWEET

038-Cycle_dsu

a guest Feb 23rd, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<stdio.h>
  2. #include<vector>
  3. using namespace std;
  4. vector<int> head(100050,0);
  5. int root(int a){
  6.     if(head[a]==a) return a;
  7.     return head[a]=root(head[a]);
  8. }
  9. void mer(int a,int b){
  10.     head[root(b)]=root(a);
  11. }
  12. bool check(int a,int b){
  13.     return root(a)==root(b);
  14. }
  15. int main()
  16. {
  17.     int n,m;
  18.     bool k=false;
  19.     scanf("%d%d",&n,&m);
  20.     for(int i=1;i<=n;i++) head[i]=i;
  21.     int u,v;
  22.     while(m--){
  23.         scanf("%d%d",&u,&v);
  24.         if(check(u,v)) k=true;
  25.         mer(u,v);
  26.     }
  27.     if(k) printf("Yes");
  28.     else printf("No");
  29.     return 0;
  30. }
  31.  
  32. root(a);
  33. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top