fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define l long
  4. #define mk make_pair
  5. #define pb push_back
  6. #define in insert
  7. #define se second
  8. #define fi first
  9. #define mod 1000000007
  10. #define watch(x) cout << (#x) << " is " << (x) << "\n"
  11. #define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
  12. #define pii pair<int,int>
  13. using namespace std;
  14. int a[100005],siz[100005];
  15. int root(int i)
  16. {
  17. 	while(i!=a[i])
  18. 	{
  19. 		i = a[i];
  20. 	}
  21. 	return i;
  22. }
  23. void uni(int x,int y)
  24. {
  25. 	if(siz[x]<siz[y])
  26. 	{
  27. 		siz[y] += siz[x];
  28. 		a[x] = a[y];
  29. 	}
  30. 	else
  31. 	{
  32. 		siz[x] += siz[y];
  33. 		a[y] = a[x];
  34. 	}
  35. }
  36. int main()
  37. {
  38.     fast;
  39.     int t;
  40.     cin>>t;
  41.     int nu=1;
  42.     while(t--)
  43.     {
  44.     	int n,m,i,ans=0;
  45.     	cin>>n>>m;
  46.     	bool vi[100005] = {false};
  47.     	for(i=1;i<=n;i++)
  48.     	{
  49.     		a[i] = i;
  50.     		siz[i] = 1;
  51.     	}
  52.     	for(i=0;i<m;i++)
  53.     	{
  54.     		int x,y;
  55.     		cin>>x>>y;
  56.     		vi[x] = true;
  57.     		vi[y] = true;
  58.     		int na = root(x);
  59.     		int ma = root(y);
  60.     		if(na!=ma)
  61.     		{
  62.     			uni(na,ma);
  63.     		    ans++;
  64.     		}
  65.     	}
  66.     	int cn=0,cc=0;
  67.     	for(i=1;i<=n;i++)
  68.     	{
  69.     		if(!vi[i]) cn++;
  70.     	}
  71.     	for(i=1;i<=n;i++)
  72.     	{
  73.     		if(i==a[i] && siz[i]>1) cc++;
  74.     	}
  75.     	ans += 2*(cn-1);
  76.     	ans += 2*cc;
  77.     	cout<<"Case"<<" "<<"#"<<nu<<":"<<" "<<ans<<"\n";
  78.     	nu++;
  79.     }
  80. }
Success #stdin #stdout 0s 4508KB
comments (?)
stdin
copy 
1
3 1
2 1
stdout
copy 
Case #1: 3
https://ideone.com/kHgVsR
language:
C++14 (gcc 8.3)
created:
4 years 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!