fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define endl '\n'
  4. int arr[2000090],size[2000090];
  5. void initialize(int n)
  6. {
  7. 	for(int i=1;i<=n;i++)
  8. 	{
  9. 		size[i]=1;
  10. 		arr[i]=i;
  11. 	}
  12. }
  13. int root(int i)
  14. {
  15. 	while(arr[i] != i)
  16. 	{
  17. 		arr[i]=arr[arr[i]];
  18. 		i=arr[i];
  19. 	}
  20. 	return i;
  21. }
  22. bool find(int a,int b)
  23. {
  24. 	if(root(a)==root(b))
  25. 		return true;
  26. 	return false;
  27. }
  28. void weighted_union(int a,int b)
  29. {
  30. 	int ra=root(a);
  31. 	int rb=root(b);
  32. 	if(ra==rb)
  33. 		return;
  34. 	if(size[ra]<size[rb])
  35. 	{
  36. 		arr[ra]=arr[rb];
  37. 		size[rb]+=size[ra];
  38. 		size[ra]=0;
  39. 	}
  40. 	else
  41. 	{
  42. 		arr[rb]=arr[ra];
  43. 		size[ra]+=size[rb];
  44. 		size[rb]=0;
  45. 	}
  46. }
  47. int main()
  48. {
  49.     ios_base::sync_with_stdio(false);
  50.     cin.tie(NULL);
  51.  
  52.       map< int,int > mp;
  53.       set<int> s;
  54.       vector< pair<int,int> > vs;
  55.       int n,m;
  56.       cin>>n>>m;
  57.       for(int i=0;i<m;i++)
  58.       {
  59.       	int x,y;
  60.       	cin>>x>>y;
  61.       	s.insert(x);
  62.       	s.insert(y);
  63.       	vs.push_back(make_pair(x,y));
  64.       }
  65.       auto it = s.begin();
  66.       int c=1;
  67.       vector<int> mem;
  68.       while(it!=s.end())
  69.       {
  70.       	mp[*it]=c;
  71.       	mem.push_back(*it);
  72.       	c++;
  73.       	it++;
  74.       }
  75.       int si=s.size(),cc=0;
  76.       initialize(si+100);
  77.       for(int i=0;i<vs.size();i++)
  78.       {
  79.       	weighted_union(mp[vs[i].first],mp[vs[i].second]);
  80.       }
  81.     for(int i=1;i<=si;i++)
  82.     {
  83.     	if(size[i]!=0)
  84.     		cc++;
  85.     }
  86.     //cout<<mem.size()<<endl;
  87.     	cc += mem[0]-1;
  88.  
  89.     for(int i=1;i<mem.size();i++)
  90.     {
  91.     	cc+= mem[i]-mem[i-1]-1;
  92.     }
  93.     cc+=n-mem[mem.size()-1];
  94.     cout<<cc<<endl;
  95.     return 0;
  96. }
Success #stdin #stdout 0s 4520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-16777216
https://ideone.com/fXY4We
language:
C++14 (gcc 8.3)
created:
6 years 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!