fork download
copy 
  1.    #include<iostream>
  2. #include<queue>
  3. #include<cstring>
  4. #include<vector>
  5. #define N 201
  6. #include<cstdio>
  7. using namespace std;
  8. vector<long long>v[N];
  9. long long m,sum,sum1;
  10. void BIPARTITE();
  11. long long check=0;
  12. int main()
  13. {
  14.  
  15. 	long long n,t,i,j,x,y,k;
  16. 	scanf("%lld",&t);
  17. 	for(i=1;i<=t;i++)
  18. 	{
  19. 		scanf("%lld",&m);
  20. 		for(j=1;j<=m;j++)
  21. 		{
  22. 			scanf("%lld",&x);
  23. 			if(x!=0)
  24. 			{
  25. 				for(k=1;k<=x;k++)
  26. 				{
  27. 				scanf("%lld",&y);
  28. 				v[j].push_back(y);
  29. 				v[y].push_back(j);
  30. 				}
  31. 			}
  32. 		}
  33. 		sum=0;
  34. 		sum1=0;
  35. 		check=0;
  36. 		BIPARTITE();
  37. 		if(check==0)
  38. 		printf("%lld\n",sum);
  39. 		else
  40. 			printf("%lld\n",sum1);
  41. 		for(j=1;j<=N;j++)
  42. 			v[j].clear();
  43. 	}
  44.  
  45.  
  46.  
  47. }
  48. void BIPARTITE()
  49. {
  50. 	long long taken[N];
  51. 	long long  color[N];
  52. 	queue<long long>q;
  53. 	memset(taken,0,sizeof(taken));
  54. 	memset(color,0,sizeof(color));
  55. 	long long c_0,c_1;
  56. 	long long i,x,y,j;
  57. 	for(i=1;i<=m;i++)
  58. 	{
  59. 		if(taken[i]!=1)
  60. 		{
  61. 			q.push(i);
  62. 			taken[i]=1;
  63. 			c_0=1,c_1=0;
  64. 			while(!q.empty())
  65. 			{
  66. 				x=q.front();
  67. 				q.pop();
  68. 				for(j=0;j<v[x].size();j++)
  69. 				{
  70. 					y=v[x][j];
  71. 					if(taken[y]!=1)
  72. 					{
  73. 						taken[y]=1;
  74. 						if(color[x]==0)
  75. 						{
  76. 							color[y]=1;
  77. 							c_1=c_1+1;
  78. 						}
  79. 						else if(color[x]==1)
  80. 						{
  81. 							color[y]=0;
  82. 							c_0=c_0+1;
  83. 						}
  84. 						q.push(y);
  85. 					}
  86. 					if(taken[y]==1)
  87. 					{
  88. 						if(color[y]==color[x])
  89. 							check=1;
  90. 					}
  91. 				}
  92. 			}
  93.  
  94. 			 if(c_0>c_1)
  95. 				 sum=sum+c_0;
  96. 			 else 
  97. 				 sum=sum+c_1;
  98. 			 if(v[x].size()==0)
  99. 				 sum1=sum1+1;
  100.  
  101. 		}
  102. 	}
  103. }
  104.  
Success #stdin #stdout 0s 3436KB
comments (?)
stdin
copy 
 1

5
5 2 4 6 8 10
3 1 3 6
0
0
3 1 6 7
stdout
copy 
0
https://ideone.com/sWsedx
language:
C++14 (gcc 8.3)
created:
9 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!