Advertisement
Saleh127

LO 1009

Oct 30th, 2020
65
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
  5. vector<ll>g[100005];
  6. ll visit[100005],c[100005];
  7. ll v,l;
  8. void dfs(ll ind)
  9. {
  10. visit[ind]=1;
  11. if(c[ind]==0) v++;
  12. else l++;
  13. for(auto i : g[ind])
  14. {
  15. if(visit[i]==0)
  16. {
  17. c[i]=(c[ind]+1)%2;
  18. dfs(i);
  19. }
  20. }
  21.  
  22. }
  23.  
  24. int main()
  25. {
  26. ios_base::sync_with_stdio(0);
  27. cin.tie(0);
  28. cout.tie(0);
  29.  
  30. test
  31. {
  32. ll n,m,i,j,k,x=0;
  33.  
  34. cin>>n;
  35.  
  36.  
  37. memset(visit,0,sizeof(visit));
  38. memset(c,0,sizeof(c));
  39.  
  40. for(i=0; i<n; i++)
  41. {
  42. cin>>k>>l;
  43. g[k].push_back(l);
  44. g[l].push_back(k);
  45. x=max(x,max(l,k));
  46. }
  47. k=0;
  48. for(i=1;i<=x;i++)
  49. {
  50. v=l=0;
  51. if(visit[i]==0 && g[i].size()>0)
  52. {
  53. c[i]=0;
  54. dfs(i);
  55. }
  56. k+=max(v,l);
  57. }
  58.  
  59. cout<<"Case "<<cs<<": "<<k<<endl;
  60.  
  61. for(i=1;i<=x;i++)
  62. {
  63. g[i].clear();
  64. }
  65. }
  66.  
  67. return 0;
  68. }
  69.  
Advertisement
RAW Paste Data Copied
Advertisement