fork download 
  1. // Errichto
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
  5. #define RI(i,n) FOR(i,1,(n))
  6. #define REP(i,n) FOR(i,0,(n)-1)
  7.  
  8. const int nax = 1e5 + 5;
  9. vector<int> w[nax];
  10. int deg[nax];
  11. bool vis[nax];
  12.  
  13. struct cmp {
  14. 	bool operator()(int a, int b) {
  15. 		if(deg[a] != deg[b]) return deg[a] < deg[b];
  16. 		return a < b;
  17. 	}
  18. };
  19. typedef set<int,cmp> cc;
  20.  
  21. void dfs(int a, cc & s) {
  22. 	s.insert(a);
  23. 	vis[a] = true;
  24. 	for(int b : w[a]) if(!vis[b]) dfs(b, s);
  25. }
  26.  
  27. int getReserve(cc & s, int m) {
  28. 	assert(!s.empty());
  29. 	auto it = s.begin();
  30. 	int reserve = m - deg[*it];
  31. 	++it;
  32. 	if(it != s.end()) reserve += m - deg[*it];
  33. 	return reserve;
  34. }
  35.  
  36. int getOne(cc & s) {
  37. 	int a = *s.begin();
  38. 	s.erase(s.begin());
  39. 	++deg[a];
  40. 	s.insert(a);
  41. 	return a;
  42. }
  43.  
  44. int main() {
  45. 	int n, m;
  46. 	scanf("%d%d", &n, &m);
  47. 	while(m--) {
  48. 		int a, b;
  49. 		scanf("%d%d", &a, &b);
  50. 		--a; --b;
  51. 		w[a].push_back(b);
  52. 		w[b].push_back(a);
  53. 		++deg[a]; ++deg[b];
  54. 	}
  55. 	m = *max_element(deg, deg + n);
  56. 	long long totalReserve = (long long) m * n - accumulate(deg, deg + n, 0);
  57.  
  58.  
  59. 	vector<cc> all;
  60. 	REP(i, n) if(!vis[i]) {
  61. 		cc s;
  62. 		dfs(i, s);
  63. 		all.push_back(s);
  64. 		bool ok = false;
  65. 		for(int a : s) if(deg[a] < m) ok = true;
  66. 		if(!ok) ++m;
  67. 	}
  68. 	while(totalReserve < 2 * (int) all.size() - 2) {
  69. 	// while(totalReserve < 2 * n - 2) {
  70. 		totalReserve += n;
  71. 		++m;
  72. 	}
  73. 	for(cc & s : all) {
  74. 		bool ok = false;
  75. 		for(int a : s) if(deg[a] < m) ok = true;
  76. 		if(!ok) ++m;
  77. 	}
  78.  
  79. 	int countConnected = all.size();
  80.  
  81. 	vector<cc> leaves, normals;
  82. 	for(cc & s : all) {
  83. 		int reserve = getReserve(s, m);
  84. 		if(reserve == 1) leaves.push_back(s);
  85. 		if(reserve > 1) normals.push_back(s);
  86. 	}
  87.  
  88. 	vector<pair<int,int>> ans;
  89. 	while(int(normals.size() + leaves.size()) >= 2) {
  90. 		if(leaves.empty()) {
  91. 			leaves.push_back(normals.back());
  92. 			normals.pop_back();
  93. 		}
  94. 		if(normals.empty()) {
  95. 			normals.push_back(leaves.back());
  96. 			leaves.pop_back();
  97. 		}
  98. 		cc & a = normals.back();
  99. 		assert(!leaves.empty());
  100. 		cc & b = leaves.back();
  101. 		ans.push_back({getOne(a), getOne(b)});
  102. 		leaves.pop_back();
  103. 		if(getReserve(a, m) == 1) {
  104. 			leaves.push_back(a);
  105. 			normals.erase(normals.end()-1);
  106. 		}
  107. 	}
  108. 	// printf("%d %d\n", (int) ans.size(), countConnected-1);
  109. 	assert((int) ans.size() == countConnected - 1);
  110. 	printf("%d\n", (int) ans.size());
  111. 	for(pair<int,int> p : ans) printf("%d %d\n", p.first+1, p.second+1);
  112. 	return 0;
  113. }
Runtime error #stdin #stdout 0s 5124KB
comments (?)
stdin 
Bear and Roads
stdout 
Standard output is empty
https://ideone.com/QNOhiQ
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!