fork(2) download
copy 
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <iostream>
  5. #include <sstream>
  6. #include <utility>
  7. #include <string>
  8. #include <cstring>
  9. #include <set>
  10. #include <queue>
  11. #include <stack>
  12. #include <cmath>
  13. #include <map>
  14. using namespace std;
  15. int t;
  16. vector <vector <int> > mat;
  17. queue <int> qu;
  18. int n,t1,t2;
  19. vector <int> vis,vis2,vis3;
  20. int bl[2];
  21. int get_max();
  22. bool check(int);
  23. void visit(int);
  24. int main()
  25. {
  26.  
  27. 	scanf("%d",&t);
  28.  
  29. 	while(t--)
  30. 	{
  31. 		scanf("%d",&n);
  32. 		mat.clear(); mat.resize(n);
  33. 		vis.resize(n); vis2.resize(n);
  34. 		for(int i=0;i<n;i++)
  35. 		{
  36. 			scanf("%d",&t1);
  37. 			vis[i]=-1;
  38. 			for(int j=0;j<t1;j++) 
  39. 			{
  40. 				scanf("%d",&t2); 
  41. 				if(t2>n) continue;
  42. 				t2--;
  43. 				mat[i].push_back(t2);
  44. 				mat[t2].push_back(i);
  45. 			}
  46. 		}
  47. 		int res=0;
  48. 		for(int i=0;i<n;i++)
  49. 		{
  50. 			if(vis[i]!=-1) continue;
  51.  
  52. 			bl[0]=1; bl[1]=0;
  53. 			while(!qu.empty()) qu.pop();
  54. 			qu.push(i);
  55. 			vis[i]=0;
  56. 			int t3=get_max();
  57. 			if(check(i)) res+=t3;
  58. 		}
  59. 		printf("%d\n",res);
  60. 	}
  61. 	return 0;
  62. }
  63.  
  64. int get_max()
  65. {
  66. 	while(!qu.empty())
  67. 	{
  68. 		t1=qu.front(); qu.pop();
  69. 		t2=vis[t1];
  70. 		if(t2) t2=0; else t2=1;
  71. 		for(int j=0;j<mat[t1].size();j++)
  72. 		{
  73. 			if(vis[mat[t1][j]]==-1)
  74. 			{
  75. 				vis[mat[t1][j]]=t2;
  76. 				bl[t2]++;
  77. 				qu.push(mat[t1][j]);
  78. 			}
  79. 		}
  80. 	}
  81. 	return (bl[0]>bl[1])?bl[0]:bl[1];
  82. }
  83.  
  84. bool check(int x)
  85. {
  86. 	for(int i=0;i<n;i++) vis2[i]=0;
  87. 	vis3.clear();
  88. 	visit(x);
  89. 	for(int i=0;i<vis3.size();i++)
  90. 	{
  91. 		for(int j=0;j<mat[i].size();j++)
  92. 		{
  93. 			if(vis[i]==vis[mat[i][j]]) return false;
  94. 		}
  95. 	}
  96. 	return true;
  97. }
  98.  
  99. void visit(int x)
  100. {
  101. 	vis2[x]=1;
  102. 	vis3.push_back(x);
  103. 	for(int i=0;i<mat[x].size();i++)
  104. 	{
  105. 		if(!vis2[mat[x][i]]) visit(mat[x][i]);
  106. 	}
  107. }
Success #stdin #stdout 0s 3440KB
comments (?)
stdin
copy 
    5

    7
    2 2 3
    1 1
    3 1 7 4
    2 7 3
    0
    0
    2 3 4


    7
    2 2 3
    0
    0
    2 5 7
    0
    1 7
    0

    10
    2 2 3
    0
    0
    2 5 7
    0
    1 7
    0
    0
    0
    2 8 9

    20
    2 2 3
    2 5 3
    1 9
    0
    1 4
    3 9 7 8
    1 8
    0
    1 10
    0
    2 13 12
    2 13 15
    1 17
    0
    0
    0
    0
    2 20 19
    1 20
    0


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