fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector<int>v[20009];
  4. queue<int>q;
  5. map<int,bool>vis,color;
  6. int main() {
  7. 	// your code goes here
  8. 	int t;
  9. 	cin>>t;
  10. 	for(int i=1;i<=t;i++)
  11. 	{
  12. 		int n,x;
  13. 		cin>>n;
  14. 		while(n--)
  15. 		{
  16. 			int u,m;
  17. 			cin>>u>>m;
  18. 			v[u].push_back(m);
  19. 			v[m].push_back(u);
  20. 			x=u;
  21. 		}
  22. 		int black=0,red=0;
  23.         color[x]=0;
  24.         red++;
  25.         q.push(x);
  26.         while(!q.empty())
  27.         {
  28.         	int s=q.front();
  29.         	q.pop();
  30.         	for(int i=0;i<v[s].size();i++)
  31.         	{
  32.         		if(!vis[v[s][i]])
  33.         		{
  34.         			if(color[s]==0)
  35.         			{
  36.         				color[v[s][i]]=1;
  37.         				black++;
  38.         			}
  39.         			else if(color[s]==1)
  40.         			{
  41.         				color[v[s][i]]=0;
  42.         				red++;
  43.         			 }
  44.         			 q.push(v[s][i]);
  45.         			 vis[v[s][i]]=1;
  46.         		}
  47.         	}
  48.         }
  49.         cout<<"Case "<<i<<":"<<" "<<max(red,black)<<endl;
  50.         for(int i=0;i<20009;i++)
  51.          v[i].clear();
  52.         vis.clear();
  53.         color.clear();
  54.      }
  55. 	return 0;
  56. }
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
2
2
1 2
2 3
3
1 2
2 3
4 2
stdout
copy 
Case 1: 2
Case 2: 4
https://ideone.com/P5qZDx
language:
C++14 (gcc 8.3)
created:
8 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!