fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <set>
  4. #include <vector>
  5. #include <cstdio>
  6. using namespace std;
  7. #define maxn 5010
  8.  
  9. vector <int> adj[maxn], qq;
  10. set <int> s;
  11. int edge[maxn][maxn], mark[maxn], deg[maxn], del[maxn], n, tot;
  12.  
  13. void reset(){
  14. 	for (int i=1; i<=n; i++){
  15. 		mark[i]= 0;
  16. 		deg[i]= adj[i].size();
  17. 		del[i]= 0;
  18. 	}   
  19. }
  20.  
  21.  
  22. void fill(){
  23. 	for (int i=1; i<=n; i++) mark[i]= 0;
  24. 	for (int i=0; i<qq.size(); i++) mark[qq[i]]= 1;
  25. }
  26.  
  27. int findans(){
  28. 	int ans= 0, sz= qq.size();
  29. 	if (sz<n and sz) ans++;
  30. 	reset();
  31. 	fill();
  32. 	for (int i=1; i<=n; i++){
  33. 		for (int j=0; j<adj[i].size(); j++){
  34. 			if (mark[adj[i][j]]) deg[i]--;
  35. 		}
  36. 	}
  37. 	for (int i=1; i<=n; i++){
  38. 		if (!mark[i] and adj[i].size()==sz-1){
  39. 			for (int j=1; j<=n; j++){
  40. 				if (!mark[j] or edge[i][j] or i==j) continue;
  41. 				if (!deg[j]) ans++;
  42. 				break;
  43. 			}	
  44. 		} 
  45. 		if (mark[i] and !deg[i] and sz>1) ans++;
  46. 	}
  47. 	return ans;
  48. }
  49.  
  50.  
  51. bool isvalid(){
  52. 	int sum= 0, sz= qq.size();
  53. 	for (int i=0; i<qq.size(); i++) sum+=adj[qq[i]].size();
  54. 	return (sum==tot+sz*(sz-1)/2);
  55.  
  56. }
  57.  
  58. bool check (int sz){
  59. 	s.clear();
  60. 	reset();
  61. 	for (int i=1; i<=n; i++){
  62. 		if (deg[i]<sz-1) {
  63. 			s.insert(i);
  64. 			del[i]= 1;
  65. 		}
  66. 	}
  67. 	int p, q, cnt= 0;
  68. 	while (!s.empty()){
  69. 		p= *s.begin();
  70. 		s.erase(s.begin());
  71. 		for (int i=0; i<adj[p].size(); i++){
  72. 			q= adj[p][i];
  73. 			deg[q]--;
  74. 			if (deg[q]<sz-1 and !del[q]) {
  75. 				s.insert(q);
  76. 				del[q]= 1;
  77. 			}
  78. 		}
  79. 	}
  80. 	for (int i=1; i<=n; i++){
  81. 		if (!del[i] and deg[i]>=sz) cnt++;
  82. 	}
  83. 	return (cnt>sz);
  84. }
  85.  
  86.  
  87. int main() {
  88. 	int k, x, sz= 0, cnt= 0, p, q, temp;
  89. 	scanf("%d", &n);
  90. 	for (int i=1; i<=n; i++){
  91. 		scanf("%d", &k);
  92. 		tot+=k;
  93. 		while (k--){
  94. 			scanf("%d", &x);
  95. 			adj[i].push_back(x);
  96. 			edge[i][x]= 1;
  97. 		}
  98. 	}
  99. 	tot/=2;
  100. 	for (int i= 20; i>=0; i--){
  101. 		temp= sz+(1<<i);
  102. 		if (temp>=n) continue;
  103. 		if (check(temp)) sz= temp;
  104. 	} 
  105. 	sz++;
  106. 	s.clear();
  107. 	reset();
  108. 	for (int i=1; i<=n; i++){
  109. 		if (deg[i]<sz-1) {
  110. 			s.insert(i);
  111. 			del[i]= 1;
  112. 		}
  113. 	}
  114.  
  115. 	while (!s.empty()){
  116. 		p= *s.begin();
  117. 		s.erase(s.begin());
  118. 		for (int i=0; i<adj[p].size(); i++){
  119. 			q= adj[p][i];
  120. 			deg[q]--;
  121. 			if (deg[q]<sz-1 and !del[q]) {
  122. 				s.insert(q);
  123. 				del[q]= 1;
  124. 			}
  125. 		}
  126. 	}
  127. 	for (int i=1; i<=n; i++){
  128. 		if (!del[i] and deg[i]>=sz){
  129. 			cnt++;
  130. 			qq.push_back(i);
  131. 		} 
  132. 	}
  133. 	if (cnt==sz){
  134. 		if (!isvalid()){
  135. 			printf("0 \n");
  136. 			return 0;
  137. 		}
  138. 		printf("%d \n", findans());
  139. 		return 0;
  140. 	}
  141. 	for (int i=1; i<=n; i++){
  142. 		if (del[i] or deg[i]>=sz) continue;
  143. 		qq.clear();
  144. 		for (int j=0; j<adj[i].size(); j++){
  145. 			if (!del[adj[i][j]]) qq.push_back(adj[i][j]);
  146. 		}
  147. 		qq.push_back(i);
  148. 		if (!isvalid()) continue;
  149. 		printf("%d \n", findans());
  150. 		return 0;
  151. 	}
  152. 	printf("0 \n");
  153. 	return 0;
  154.  
  155.  
  156. }
Success #stdin #stdout 0s 113472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/OzM4oA
language:
C++14 (gcc 8.3)
created:
8 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!