fork download
copy 
  1. // i wants to take ioi
  2. //binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. #define int long long
  8. #define nn "\n"
  9. #define pi pair<int, int>
  10. #define fi first
  11. #define se second
  12. #define lb lower_bound
  13. #define ub upper_bound
  14. #define eb emplace_back
  15. #define pb push_back
  16. #define TASK " "
  17.  
  18. #define ms(a, x) memset(a, x, sizeof(a))
  19. #define all(a) a.begin(), a.end()
  20. #define All(a, n) a + 1, a + 1 + n
  21.  
  22. #define LOG 19
  23.  
  24.  
  25. const int INF = 1e18;
  26. const int mod = 1e9;
  27. const int N = 1e3  + 5;
  28. int MOD = 998244353;
  29. int bit[200000];
  30. struct node{
  31. 	int kc, u, hk;
  32. 	bool operator<(const node& other) const {
  33.         return kc > other.kc;
  34.     }
  35. };
  36. struct edge{
  37. 	int v, w, h;
  38. };
  39. int n;
  40. struct edges{
  41.     int a, b;
  42. } canh[N];
  43. int sz[N], par[N];
  44.  
  45. void make_set(int s){
  46.     sz[s] = 1;
  47.     par[s] = s;
  48. }
  49. int get(int s){
  50.     if(par[s] == s) return s;
  51.     return par[s] = get(par[s]);
  52. }
  53. void union_set(int a, int b){
  54.     a = get(a);
  55.     b = get(b);
  56.     if(a != b){
  57.         if(sz[a] < sz[b]) swap(a, b);
  58.         par[b] = a;
  59.         sz[a] += sz[b];
  60.     }
  61. }
  62. void nhap(){
  63.     cin >> n;
  64.     for(int i = 1; i <= n - 1; i++){
  65.         cin >> canh[i].a >> canh[i].b;
  66.     }
  67. }
  68. vector<pi> v;
  69. vector<pi> vt;
  70. void solve(){
  71.     for(int i = 1; i <= n; i++){
  72.         make_set(i);
  73.     }
  74.     for(int i = 1; i < n; i++){
  75.         if(get(canh[i].a) != get(canh[i].b)){
  76.             union_set(canh[i].a, canh[i].b);
  77.         }
  78.         else{
  79.             v.eb(canh[i].a, canh[i].b);
  80.         }
  81.     }
  82.     for(int i = 1; i <= n; i++){
  83.         for(int j = 1; j <= n; j++){
  84.             if(i != j){
  85.                 if(get(i) != get(j)){
  86.                     union_set(i, j);
  87.                     vt.eb(i, j);
  88.                 }
  89.             }
  90.         }
  91.     }
  92.     cout << v.size() << nn;
  93.     for(int i = 0; i < v.size(); i++){
  94.         cout << v[i].fi << " " << v[i].se << " " << vt[i].fi << " " << vt[i].se << nn;
  95.     }
  96. }
  97. signed main() {
  98. 	// freopen("piggyback.in", "r", stdin);
  99. 	// freopen("piggyback.out", "w", stdout);
  100. 	ios_base::sync_with_stdio(0);
  101. 	cin.tie(0);
  102. 	cout.tie(0);
  103. 	nhap();
  104. 	solve();
  105. 	return (0 ^ 0);
  106.  
  107. }
  108.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
2
0 5
5 0
1
1 2 3
stdout
copy 
1
0 5 1 2
https://ideone.com/levqlh
language:
C++14 (gcc 8.3)
created:
14 hours 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!