fork(1) download
  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
stdin
2
2
1 2
2 3
3
1 2
2 3
4 2
stdout
Case 1: 2
Case 2: 4