fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int max_gal = 100007;
  5. int rep[max_gal];
  6. int ile_w[max_gal];
  7. int ile_k[max_gal];
  8.  
  9.  
  10. int Find(int a){
  11.  
  12. 	if(rep[a] == a){
  13. 		return a;
  14. 	}
  15. 	rep[a] = Find(rep[a]);
  16. 	return (rep[a]);
  17. }
  18.  
  19. void Union(int a,int b){
  20.     if(Find(a) == Find(b))
  21.     {
  22.         ile_k[Find(b)]++;
  23.     }
  24.     else{
  25.     ile_k[Find(b)] += ile_k[Find(a)]+1;
  26.     ile_k[Find(a)] = 0;
  27.     ile_w[Find(b)] += ile_w[Find(a)];
  28.     ile_w[Find(a)] = 0;}
  29. 	rep[Find(a)] = rep[Find(b)];
  30. }
  31.  
  32. int main()
  33. {
  34.     ios_base::sync_with_stdio(0);
  35.     int n,m,a,b,wyn = 1;
  36.  
  37.     cin >> n >> m;
  38. 	for(int i=1;i <= 100001;++i){
  39. 		rep[i] =i;
  40.         ile_w[i] = 1;
  41. 		ile_k[i] = 0;
  42.  
  43. 	}
  44.     for(int i = 0;i < m;++i)
  45.     {
  46.         cin >> a >> b;
  47.         Union(a,b);
  48.  
  49.     }
  50.     set<int> czy;
  51.     for(int i = 1;i <= n;++i)
  52.     {
  53.     	if(czy.find(Find(i)) == czy.end())
  54.     	{
  55.     		wyn += max(ile_k[Find(i)]-ile_w[Find(i)]+1,0);
  56.     		czy.insert(Find(i));
  57.     	}
  58.  
  59.     }
  60.     cout << wyn;
  61. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin 
3 2
1 3
1 2
stdout 
1
https://ideone.com/lXaXut
language:
C++14 (gcc 8.3)
created:
11 days ago
visibility:
public

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!