fork download
copy 
  1. // iostream is too mainstream
  2. #include <cstdio>
  3. // bitch please
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <cstdlib>
  7. #include <vector>
  8. #include <set>
  9. #include <map>
  10. #include <queue>
  11. #include <stack>
  12. #include <list>
  13. #include <cmath>
  14. #include <iomanip>
  15. #include <time.h>
  16. #define dibs reserve
  17. #define OVER9000 1034567890
  18. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  19. #define tisic 47
  20. #define soclose 1e-9
  21. #define chocolate win
  22. // so much chocolate
  23. #define patkan 9
  24. #define ff first
  25. #define ss second
  26. #define abs(x) ((x < 0)?-(x):x)
  27. #define uint unsigned int
  28. #define dbl long double
  29. using namespace std;
  30. // mylittledoge
  31.  
  32. /* Edmonds' blossom algorithm
  33. match[v]: vertex matched to it / -1
  34. finds a tree of alternating paths rooted at R; the parent of v is prev[v] or match[v]
  35. also builds a tree of blossoms
  36. 'k, I say blossoms, but each blossom = its base
  37. */
  38.  
  39. // based on https://sites.google.com/site/indy256/algo/edmonds_matching
  40.  
  41. int lca(vector<int> &cur_blossom, vector<int> &match, vector<int> &prev, int u, int v) {
  42. 	// in the tree of blossoms
  43. 	// lists blossoms on paths to the root, finds the first common one
  44. 	set<int> blossoms_visited;
  45.  
  46. 	int b =cur_blossom[u];
  47. 	while(true) {
  48. 		blossoms_visited.insert(b);
  49. 		if(match[b] == -1 || prev[match[b]] == -1) break;
  50. 		b =cur_blossom[prev[match[b]]];}
  51.  
  52. 	b =cur_blossom[v];
  53. 	while(true) {
  54. 		if(blossoms_visited.find(b) != end(blossoms_visited)) return b;
  55. 		b =cur_blossom[prev[match[b]]];}
  56.  
  57. 	return b;}
  58.  
  59. int find_aug_path(vector< vector<int> > &G, vector<int> &match, vector<int> &prev, int R) {
  60. 	int N =G.size();
  61. 	vector<bool> vis(N,false);
  62.  
  63. 	vector<int> cur_blossom(N);
  64. 	for(int i =0; i < N; i++) cur_blossom[i] =i;
  65.  
  66. 	queue<int> q;
  67. 	q.push(R);
  68. 	vis[R] =true;
  69.  
  70. 	while(!q.empty()) {
  71.  
  72. 		ALL_THE(G[q.front()],it) if(*it != match[q.front()]) {
  73.  
  74. 			// in the same blossom, already processed
  75. 			if(cur_blossom[*it] == cur_blossom[q.front()]) continue;
  76.  
  77. 			if(prev[*it] == -1 && !(match[*it] != -1 && prev[match[*it]] != -1)) {
  78. 				if(*it == R) continue;
  79. 				prev[*it] =q.front();
  80. 				if(match[*it] == -1) return (*it); // augmenting path to *it
  81. 				vis[match[*it]] =true;
  82. 				q.push(match[*it]);
  83. 				continue;}
  84.  
  85. 			if(*it != R && !(match[*it] != -1 && prev[match[*it]] != -1)) continue;
  86.  
  87. 			// blossom found
  88.  
  89. 			int new_blossom =lca(cur_blossom,match,prev,q.front(),*it);
  90. 			vector<bool> in_new_blossom(N,false);
  91.  
  92. 			int v =q.front(), parent_v =*it;
  93. 			while(cur_blossom[v] != new_blossom) {
  94. 				in_new_blossom[cur_blossom[v]] =in_new_blossom[cur_blossom[match[v]]] =true;
  95. 				prev[v] =parent_v;
  96. 				parent_v =match[v];
  97. 				v =prev[match[v]];}
  98.  
  99. 			v =*it, parent_v =q.front();
  100. 			while(cur_blossom[v] != new_blossom) {
  101. 				in_new_blossom[cur_blossom[v]] =in_new_blossom[cur_blossom[match[v]]] =true;
  102. 				prev[v] =parent_v;
  103. 				parent_v =match[v];
  104. 				v =prev[match[v]];}
  105.  
  106. 			for(int i =0; i < N; i++) if(in_new_blossom[cur_blossom[i]]) {
  107. 				cur_blossom[i] =new_blossom;
  108. 				if(vis[i]) continue;
  109. 				vis[i] =true;
  110. 				q.push(i);}
  111.  
  112. 			}
  113.  
  114. 		q.pop();}
  115.  
  116. 	return -1;}
  117.  
  118. vector<bool> find_winning(vector< vector<int> > &G, vector<int> &match, vector<int> &prev, int R) {
  119. 	// find all vertices ending at even length alternating paths
  120. 	int N =G.size();
  121. 	vector<bool> is_winning(N,false);
  122. 	is_winning[R] =true;
  123. 	vector<bool> vis(N,false);
  124.  
  125. 	vector<int> cur_blossom(N);
  126. 	for(int i =0; i < N; i++) cur_blossom[i] =i;
  127.  
  128. 	queue<int> q;
  129. 	q.push(R);
  130. 	vis[R] =true;
  131.  
  132. 	while(!q.empty()) {
  133.  
  134. 		ALL_THE(G[q.front()],it) if(*it != match[q.front()]) {
  135.  
  136. 			// in the same blossom, already processed
  137. 			if(cur_blossom[*it] == cur_blossom[q.front()]) continue;
  138.  
  139. 			if(prev[*it] == -1 && !(match[*it] != -1 && prev[match[*it]] != -1)) {
  140. 				if(*it == R) continue;
  141. 				prev[*it] =q.front();
  142. 				vis[match[*it]] =true;
  143. 				is_winning[match[*it]] =true;
  144. 				q.push(match[*it]);
  145. 				continue;}
  146.  
  147. 			if(*it != R && !(match[*it] != -1 && prev[match[*it]] != -1)) continue;
  148.  
  149. 			// blossom found
  150.  
  151. 			int new_blossom =lca(cur_blossom,match,prev,q.front(),*it);
  152. 			vector<bool> in_new_blossom(N,false);
  153.  
  154. 			int v =q.front(), parent_v =*it;
  155. 			while(cur_blossom[v] != new_blossom) {
  156. 				in_new_blossom[cur_blossom[v]] =in_new_blossom[cur_blossom[match[v]]] =true;
  157. 				prev[v] =parent_v;
  158. 				parent_v =match[v];
  159. 				v =prev[match[v]];}
  160.  
  161. 			v =*it, parent_v =q.front();
  162. 			while(cur_blossom[v] != new_blossom) {
  163. 				in_new_blossom[cur_blossom[v]] =in_new_blossom[cur_blossom[match[v]]] =true;
  164. 				prev[v] =parent_v;
  165. 				parent_v =match[v];
  166. 				v =prev[match[v]];}
  167.  
  168. 			for(int i =0; i < N; i++) if(in_new_blossom[cur_blossom[i]]) {
  169. 				cur_blossom[i] =new_blossom;
  170. 				is_winning[i] =true;
  171. 				if(vis[i]) continue;
  172. 				vis[i] =true;
  173. 				q.push(i);}
  174.  
  175. 			}
  176.  
  177. 		q.pop();}
  178.  
  179. 	return is_winning;}
  180.  
  181. int main() {
  182. 	cin.sync_with_stdio(0);
  183. 	cin.tie(0);
  184. 	int T;
  185. 	cin >> T;
  186. 	for(int t =0; t < T; t++) {
  187. 		int N,M;
  188. 		cin >> N >> M;
  189. 		vector< vector<int> > G(N);
  190. 		for(int i =0; i < M; i++) {
  191. 			int a,b;
  192. 			cin >> a >> b;
  193. 			G[--a].push_back(--b);
  194. 			G[b].push_back(a);}
  195.  
  196. 		// random maximal matching
  197. 		vector<int> match(N,-1);
  198. 		int ans =0, matching_sz =0;
  199. 		while(true) {
  200. 			// find all vertices that can matched
  201. 			vector<int> v;
  202. 			for(int i =0; i < N; i++) if(match[i] == -1) {
  203. 				bool m =false; // can it be matched?
  204. 				ALL_THE(G[i],it) if(match[*it] == -1) m =true;
  205. 				if(m) v.push_back(i);}
  206. 			if(v.empty()) break; // is maximal
  207. 			int x =v[rand()%v.size()];
  208. 			vector<int> w;
  209. 			ALL_THE(G[x],it) if(match[*it] == -1) w.push_back(*it);
  210. 			int y =w[rand()%w.size()];
  211. 			// match edge x-y
  212. 			matching_sz++;
  213. 			match[x] =y;
  214. 			match[y] =x;}
  215.  
  216. 		// make it maximum
  217. 		for(int i =0; i < N; i++) if(match[i] == -1) {
  218. 			vector<int> prev(N,-1);
  219. 			int akt =find_aug_path(G,match,prev,i); // end of the found aug. path 
  220. //			cout << i << " " << akt << "  ";
  221. //			for(int j =0; j < N; j++) cout << prev[j] << " ";
  222. //			cout << endl;
  223. 			if(akt == -1) continue;
  224. 			while(akt != -1) {
  225. 				int prev_akt =match[prev[akt]];
  226. 				match[akt] =prev[akt];
  227. 				match[prev[akt]] =akt;
  228. 				akt =prev_akt;}
  229. 			matching_sz++;}
  230.  
  231. //		cout << 2*matching_sz << " " << N << "\n";
  232.  
  233. 		vector<bool> is_winning(N,false);
  234. 		for(int i =0; i < N; i++) if(match[i] == -1) {
  235. 			vector<int> prev(N,-1);
  236. 			vector<bool> v =find_winning(G,match,prev,i);
  237. 			for(int j =0; j < N; j++) if(v[j]) is_winning[j] =true;}
  238.  
  239. 		for(int i =0; i < N; i++) if(is_winning[i]) ans++;
  240. 		cout << ans << "\n";
  241. 	}
  242. 	return 0;}
  243.  
  244. // look at my code
  245. // my code is amazing
  246.  
Success #stdin #stdout 0s 3288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/envPZl
Codechef JULY15, problem HAMILG
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!