fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. int n;
  27. vector< vector<int> > g;
  28.  
  29. vector<int> solve(vector<int> num)
  30. {
  31. 	int i,j;
  32. 	int n=num.size();
  33. 	if(n==1)
  34. 		return vector<int>(1,0);
  35. 	vector<int> in(n,0);
  36. 	vector<int> ans(n,0);
  37. 	REP2(i,0,n)
  38. 	{
  39. 		int u=num[i];
  40. 		REP2(j,0,n)
  41. 		{
  42. 			if(i==j)
  43. 				continue;
  44. 			int v=num[j];
  45. 			if(g[u][v])
  46. 				++in[i];
  47. 		}
  48. 	}
  49. 	int s=-1;
  50. 	REP2(i,0,n)
  51. 		if(in[i]%2==1)
  52. 		{
  53. 			s=i;
  54. 			break;
  55. 		}
  56. 	if(s==-1)
  57. 		return ans;
  58. 	vector<int> res;
  59. 	int top=0;
  60. 	REP2(j,0,n)
  61. 	{
  62. 		if(j==s)
  63. 			continue;
  64. 		if(g[num[s]][num[j]]==1)
  65. 			in[top]=-1;
  66. 		res.pb(num[j]);
  67. 		top++;
  68. 	}
  69. 	REP2(i,0,n-1)
  70. 		REP2(j,0,n-1)
  71. 			if(i!=j && in[i]==-1 && in[j]==-1)
  72. 				g[res[i]][res[j]]^=1;
  73. 	vector<int> tmp=solve(res);
  74. 	REP2(i,0,n-1)
  75. 		REP2(j,0,n-1)
  76. 			if(i!=j && in[i]==-1 && in[j]==-1)
  77. 				g[res[i]][res[j]]^=1;
  78. 	int sum[2]={0,0};
  79. 	REP2(i,0,n-1)
  80. 		if(in[i]==-1)
  81. 			++sum[ tmp[i] ];
  82. 	int lab=-1;
  83. 	REP2(i,0,2)
  84. 		if(sum[i]%2==0)
  85. 			lab=i;
  86. 	ans.clear();
  87. 	top=0;
  88. 	REP2(j,0,n)
  89. 		if(j==s)
  90. 			ans.pb(lab);
  91. 		else ans.pb(tmp[top++]);
  92. 	return ans;
  93. }
  94.  
  95. int main()
  96. {
  97. 	int i,j;
  98. 	scanf("%d",&n);
  99. 	g=vector< vector<int> >(n, vector<int>(n,0) );
  100. 	vector<int> num;
  101. 	REP2(i,0,n)
  102. 	{
  103. 		int l;
  104. 		scanf("%d",&l);
  105. 		while(l--)
  106. 		{
  107. 			scanf("%d",&j);
  108. 			--j;
  109. 			g[i][j]=1;
  110. 		}
  111. 		num.pb(i);
  112. 	}
  113. 	vector<int> ans=solve(num);
  114. 	int sum=0;
  115. 	REP2(i,0,(int)ans.size())
  116. 		if(ans[i])
  117. 			++sum;
  118. 	printf("%d\n",sum);
  119. 	REP2(i,0,(int)ans.size())
  120. 		if(ans[i])
  121. 			printf("%d ",i+1);
  122. 	printf("\n");
  123. 	return 0;
  124. }
Success #stdin #stdout 0s 3352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/HGJ372
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

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!