fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3.  
  4. using namespace std;
  5.  
  6. const int MOD = 1e9 + 7;
  7.  
  8. void solve(){
  9. 	int n;
  10. 	cin >> n;
  11.  
  12. 	vector<int> par(n, 0), sz(n, 1);
  13. 	set<int> trees;
  14. 	set<int> not_trees;
  15.  
  16.  
  17. 	for(int i =0; i < n; i++){
  18. 		par[i] = i;
  19. 		trees.insert(i);
  20. 	}
  21.  
  22. 	vector<vector<pair<int, int>>> c_edges(n, vector<pair<int, int>>());
  23.  
  24. 	auto find = [&](int x, auto && self) -> int {
  25. 		if(par[x] == x)return x;
  26. 		return par[x] = self(par[x], self);
  27. 	};
  28.  
  29. 	auto merge = [&](int p, int q) -> void {
  30. 		int x = find(p, find);
  31. 		int y = find(q, find);
  32.  
  33. 		if(x == y){
  34. 			c_edges[x].push_back(make_pair(p, q));
  35. 			not_trees.insert(x);
  36. 			if(trees.find(x) != trees.end())trees.erase(trees.find(x));
  37. 		}else{
  38. 			if(sz[x] < sz[y])swap(x, y);
  39. 			par[y] = x;
  40. 			sz[x] += sz[y];
  41. 			for(auto edge: c_edges[y]){
  42. 				c_edges[x].push_back(edge);
  43. 			}
  44. 			if(not_trees.find(y) != not_trees.end())not_trees.erase(not_trees.find(y));
  45. 			if(trees.find(y) != trees.end())trees.erase(trees.find(y));
  46. 			if(c_edges[x].size() == 0){
  47. 				trees.insert(x);
  48. 				if(not_trees.find(x) != not_trees.end())not_trees.erase(not_trees.find(x));
  49. 			}else{
  50. 				not_trees.insert(x);
  51. 				if(trees.find(x) != trees.end())trees.erase(trees.find(x));
  52. 			}
  53. 		}
  54. 	};
  55.  
  56.  
  57. 	for(int i = 0; i < n - 1; i++){
  58. 		int x, y;
  59. 		cin >> x >> y;
  60. 		x--;
  61. 		y--;
  62. 		merge(x, y);
  63.  
  64. 	}
  65.  
  66. 	vector<vector<int>> ans;
  67.  
  68. 	while(not_trees.size()){
  69. 		int g = *(not_trees.begin());
  70. 		int h = *(trees.begin());
  71. 		auto [r,s] = c_edges[g].back();
  72. 		c_edges[g].pop_back();
  73. 		ans.push_back({r, s, r, h});
  74. 		merge(g, h);
  75.  
  76. 	}
  77.  
  78. 	cout << ans.size() << "\n";
  79.  
  80. 	for(auto x: ans){
  81. 		for(auto y: x){
  82. 			cout << y + 1 << " ";
  83. 		}
  84. 		cout << "\n";
  85. 	}
  86.  
  87.  
  88. }
  89.  
  90. int main(){
  91. 	ios_base::sync_with_stdio(false);
  92. 	cin.tie(nullptr);
  93.  
  94. 	int t = 1;
  95. 	// cin >> t;
  96.  
  97. 	for(int i = 1; i <= t; i++){
  98. 		solve();
  99. 	}
  100. 	return 0;
  101. }
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
6
1 2
2 3
3 1
2 1
4 5
stdout
copy 
2
2 1 2 4 
3 1 3 6
https://ideone.com/xLmS4r
language:
C++ 4.3.2 (gcc-4.3.2)
created:
59 days 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!