Advertisement
Falak_Ahmed_Shakib

DSU

Mar 27th, 2023 (edited)
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.98 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef unsigned long long ull;
  5. typedef pair<ll,ll>pll;
  6. typedef pair<ll,pair<ll,ll>>plll;
  7. #define bismillah; (ios_base:: sync_with_stdio(false),cin.tie(NULL));
  8. #define vll(v) v.begin(),v.end()
  9. #define all(x) x.rbegin(),x.rend()
  10. #define min3(a, b, c) min(a, min(b, c))
  11. #define max3(a, b, c) max(a, max(b, c))
  12. #define pb push_back
  13. #define eb emplace_back
  14. #define ff first
  15. #define ss second
  16. /// DSU
  17. const int N=1e5+10;
  18. ll p[N+10];
  19. ll sz[N+10];
  20. void make(int v){
  21. p[v]=v;
  22. sz[v]=1;
  23. }
  24. int fnd(int v){
  25. if(v==p[v])return v;
  26. return p[v]=fnd(p[v]);
  27. }
  28. void Union(int a,int b){
  29. a=fnd(a);
  30. b=fnd(b);
  31. if(a!=b){
  32. if(sz[a]<sz[b])swap(a,b);
  33. p[b]=a;
  34. sz[a]+=sz[b];
  35. }
  36. }
  37.  
  38. int main(){
  39. ll n,m;
  40. cin>>n>>m;
  41. for(ll i=1;i<=n;i++)make(i);
  42. while(m--){
  43. ll a,b;
  44. cin>>a>>b;
  45. Union(a,b);
  46. }
  47. ll cnt=0;
  48. for(ll i=1;i<=n;i++)if(i==p[i])cnt++;
  49. cout<<cnt<<endl;
  50. }
  51.  
  52.  
  53.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement