SHARE
TWEET

google kickstart cherries mesh

a guest Aug 25th, 2019 36 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. #include <bits/stdc++.h>
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <cmath>
  6. #include <cstring>
  7. #include <chrono>
  8. #include <complex>
  9. #define endl "\n"
  10. #define ll long long int
  11. #define vi vector<int>
  12. #define vll vector<ll>
  13. #define vvi vector < vi >
  14. #define pii pair<int,int>
  15. #define pll pair<long long, long long>
  16. #define mod 1000000007
  17. #define inf 1000000000000000001;
  18. #define all(c) c.begin(),c.end()
  19. #define mp(x,y) make_pair(x,y)
  20. #define mem(a,val) memset(a,val,sizeof(a))
  21. #define eb emplace_back
  22. #define f first
  23. #define s second
  24. using namespace std;
  25.  
  26.  
  27. // Disjoint Set DataStructure
  28. map< ll,ll > parent;        // reserve space for map if n > 10000
  29. map< ll,ll > urank;
  30. void create(ll x)
  31. {
  32.     parent[x] = x;
  33.     urank[x] = 1;       // rank = no. of nodes in its subtree
  34. }
  35. ll find(ll x)
  36. {
  37.     if( parent[x] != x )    //path compression
  38.     {
  39.         parent[x] = find(parent[x]) ;
  40.     }
  41.     return parent[x];
  42. }
  43. void merge(ll x, ll y)
  44. {
  45.     ll xroot = find(x);
  46.     ll yroot = find(y);
  47.     if( urank[xroot] <= urank[yroot] )  // Union by rank
  48.     {
  49.         parent[xroot] = yroot ;
  50.         urank[yroot] = urank[yroot] + urank[xroot] ;
  51.     }
  52.     else
  53.     {
  54.         parent[yroot] = xroot;
  55.         urank[xroot] = urank[xroot] + urank[yroot] ;
  56.     }
  57. }
  58.  
  59.  
  60. int main()
  61. {
  62.     int T;
  63.     cin>>T;
  64.     for(int t=1;t<=T;t++)
  65.     {
  66.  
  67.         int n,m;
  68.  
  69.         cin>>n>>m;
  70.  
  71.         for(int i=0; i<n; i++) create(i);
  72.  
  73.         int black=0,red=0;
  74.  
  75.         for(int i=0; i<m; i++){
  76.             int u,v;
  77.             cin>>u>>v;
  78.  
  79.             if(find(u-1)!=find(v-1)){
  80.                 ++black;
  81.                 merge(u-1,v-1);
  82.             }
  83.         }
  84.  
  85.         for(int i=0; i<n; i++){
  86.             if(find(i)==i) red++;
  87.         }
  88.  
  89.         ll ans = black+(red-1)*2;
  90.         cout<<"Case #"<<t<<": "<<ans<<endl;
  91.     }
  92.     return 0;
  93. }
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