Advertisement
PSYCHAMERON

yoYo

Aug 4th, 2016
232
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.16 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int par[105];
  5.  
  6. struct side
  7. {
  8.     int from,to;
  9. } get;
  10.  
  11. int findset(int r)
  12. {
  13.     if(par[r] == r) return r;
  14.     return par[r] = findset(par[r]);
  15. }
  16. void setunion(int a, int b)
  17. {
  18.     int u = findset(a);
  19.     int v = findset(b);
  20.  
  21.     if(u == v) printf("They are already friends\n");
  22.     else par[u] = v;
  23. }
  24. int main()
  25. {
  26.     int u,v,n,a,b,i,j,arr[100] ;
  27.     vector<side> vec;
  28.  
  29.     scanf("%d",&n);
  30.     for(i = 1; i <= 100; i++)
  31.     {
  32.         par[i] = i;
  33.     }
  34.  
  35.     for(i = 0; i < n; i++)
  36.     {
  37.         scanf("%d %d",&a,&b);
  38.         get.from =  a;
  39.         get.to   =  b;
  40.         vec.push_back(get);
  41.     }
  42.  
  43.     for(i = 0; i < n; i++)
  44.     {
  45.         u = vec[i].from;
  46.         v = vec[i].to;
  47.         setunion(u,v);
  48.     }
  49.  
  50.     for(i = 1; i <= 10; i++) printf("Parent of %d is %d\n", i, par[i]);
  51.     cout << endl;
  52.     for(i = 1; i <= 10; i++) printf("Set of %d is %d\n", i, findset(i)); // call findset for 10 elements
  53.     cout << endl;
  54.     for(i = 1; i <= 10; i++) printf("Parent of %d is %d\n", i, par[i]);
  55.  
  56.     return 0;
  57. }
  58. /*
  59. Inputs
  60. 6
  61. 1 2
  62. 2 3
  63. 4 5
  64. 6 7
  65. 10 9
  66. 9 8
  67. 3
  68. 1 2
  69. 2 3
  70. 3 4
  71. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement