Saleh127

UVA 1197 / Disjoint set Unior

Aug 12th, 2021 (edited)
160
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.10 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  5.  
  6. map<ll,ll>parent;
  7. map<ll,ll>siz;
  8. map<ll,bool>frnd;
  9. ll ans;
  10.  
  11. ll findset(ll v)
  12. {
  13. if (v == parent[v])
  14. {
  15. return v;
  16. }
  17. return parent[v] = findset(parent[v]);
  18. }
  19.  
  20. void unionn(ll a,ll b)
  21. {
  22. a = findset(a);
  23. b = findset(b);
  24.  
  25. if(a==b) return;
  26.  
  27. else
  28. {
  29. if(siz[a]<siz[b]) swap(a,b);
  30.  
  31. parent[b]=a;
  32.  
  33. siz[a]+=siz[b];
  34. }
  35. }
  36.  
  37. int main()
  38. {
  39. ios_base::sync_with_stdio(0);
  40. cin.tie(0);
  41. cout.tie(0);
  42.  
  43. ll a,b;
  44.  
  45. ll n,m,i,j,k=1,l;
  46.  
  47. while(cin>>n>>m && (n+m)>0)
  48. {
  49. for(i=0; i<n+4; i++)
  50. {
  51. parent[i]=i;
  52. siz[i]=1ll;
  53. }
  54.  
  55.  
  56. for(i=0; i<m; i++)
  57. {
  58. cin>>k>>l;
  59. k--;
  60. while(k--)
  61. {
  62. cin>>a;
  63.  
  64. unionn(l,a);
  65. }
  66. }
  67.  
  68. cout<<siz[findset(0)]<<endl;
  69.  
  70. parent.clear();
  71. siz.clear();
  72.  
  73. }
  74.  
  75. return 0;
  76. }
Add Comment
Please, Sign In to add comment