fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long int ll;
  5. typedef unsigned long long int ull;
  6.  
  7. //WRONG ANSWER
  8.  
  9. #define MOD 1000000007
  10. #define _FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  11.  
  12. ll node, edge, par[300005];
  13. map<ll, ll> mp;
  14.  
  15. ll find_par(ll r){
  16. if(par[r] == r){
  17. return r;
  18. }
  19. else return par[r] = find_par(par[r]);
  20. }
  21.  
  22. void union_find(ll x, ll y){
  23. ll u = find_par(x);
  24. ll v = find_par(y);
  25.  
  26. if(u != v){
  27. par[v] = u;
  28. }
  29. }
  30.  
  31.  
  32. int main() {
  33.  
  34. _FastIO;
  35.  
  36. while(cin >> node >> edge){
  37. for(int i = 1; i <= 300005; i++){
  38. par[i] = i;
  39. }
  40. ll cnt = 0;
  41. while(edge--){
  42. ll x, y;
  43. cin >> x >> y;
  44.  
  45. if(mp[x] == 0){
  46. mp[x] = ++cnt;
  47. }
  48. if(mp[y] == 0){
  49. mp[y] = ++cnt;
  50. }
  51. union_find(mp[x], mp[y]);
  52. }
  53. ll ans = 0;
  54. for(ll i = 1; i <= cnt; i++){
  55. ll p = find_par(i);
  56. if(p == i){
  57. ans++;
  58. }
  59. }
  60. ans += (node-cnt);
  61. cout << ans << endl;
  62. mp.clear();
  63. }
  64.  
  65.  
  66. return 0;
  67. }
Success #stdin #stdout 0s 4376KB
stdin
Standard input is empty
stdout
Standard output is empty