fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long int ll;
  5. typedef unsigned long long int ull;
  6. #define IOS ios_base::sync_with_stdio(0);  cin.tie(0); cout.tie(0);
  7.  
  8. typedef pair<int,int>pr;
  9. #define mp   make_pair
  10. #define all(i)     i.begin() , i.end()
  11. #define ft     first
  12. #define sn     second
  13. #define pb push_back
  14. #define eps 1e-9
  15. #define SP cout<<fixed<<setprecision(10);
  16.  
  17. #define inf 100000
  18. #define MAXN 200010
  19.  
  20. const int mod = 1e9+7;
  21.  
  22. #define dbg cout<<"rony\n";
  23. #define en "\n"
  24.  
  25. vector<int>g[MAXN];
  26. int vis[MAXN];
  27.  
  28. void dfs(int nd)
  29. {
  30.     vis[nd]  = 1;
  31.     for(auto i:g[nd])
  32.     {
  33.         if(vis[i] == 1) continue;
  34.         dfs(i);
  35.     }
  36. }
  37. void solve()
  38. {
  39.   int n,m;
  40.   cin >> n >> m;
  41.   map<int,int>ma;
  42.   int cnt = 1;
  43.  
  44.   for(int i = 1;i <= m;i++)
  45.   {
  46.      int x,y;
  47.      cin >> x >> y;
  48.      if(ma[x] == 0)
  49.      {
  50.         ma[x] = cnt;
  51.         cnt++;
  52.      }
  53.      if(ma[y] == 0)
  54.      {
  55.         ma[y] = cnt;
  56.         cnt++;
  57.      }
  58.  
  59.      g[ma[x]].pb(ma[y]);
  60.      g[ma[y]].pb(ma[x]);
  61.   }
  62.  
  63.   int an = n - cnt + 1;
  64.  
  65.   for(int i = 1;i < cnt;i++)
  66.   {
  67.      if(vis[i] == 0)
  68.      {
  69.         an++;
  70.         dfs(i);
  71.      }
  72.   }
  73.   cout<<an<<en;
  74.  
  75. }
  76.  
  77. int main()
  78. {
  79.     IOS;
  80.     int t;
  81.   //cin >> t;
  82.   t = 1;
  83.     while ( t-- )
  84.     {
  85.  
  86.         solve();
  87.     }
  88.     return 0;
  89. }
  90.  
Success #stdin #stdout 0.01s 8360KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/6vpsNI
problem FOXLINGS, based on SPOJ submission 30094378 (CPP14), 2022-09-25 15:17:08
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!