fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int maxn = 1e7 + 68;
  6. const long long nuLL = LLONG_MIN;
  7.  
  8. struct DSU {
  9.         int par[maxn];
  10.  
  11.         void init(int n) {
  12.                 for (int i = 1 ; i <= n ; i++) par[i] = i;
  13.         }
  14.  
  15.         int find(int u) {
  16.                 return par[u] == u ? u : par[u] = find(par[u]);
  17.         }
  18.  
  19.         bool join(int u , int v) {
  20.                 u = find(u);
  21.                 v = find(v);
  22.  
  23.                 if (u == v) return false;
  24.  
  25.                 par[u] = v;
  26.                 return true;
  27.         }
  28. } dsu;
  29.  
  30. mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
  31.  
  32. long long rand(long long l , long long r) {
  33.         assert(l <= r);
  34.         return uniform_int_distribution<long long>(l , r)(rd);
  35. }
  36.  
  37. int u , v;
  38. vector<pair<int , int>> list_edge;
  39.  
  40. void rand_tree(int n , long long stW = nuLL , long long enW = nuLL) {
  41.         dsu.init(n);
  42.         list_edge.clear();
  43.  
  44.         for (int i = 1 ; i < n ; i++) {
  45.                 u = rand(1 , n);
  46.                 v = rand(1 , n);
  47.                 while (dsu.join(u , v) == false) {
  48.                         u = rand(1 , n);
  49.                         v = rand(1 , n);
  50.                 }
  51.  
  52.                 list_edge.push_back(make_pair(u , v));
  53.         }
  54.  
  55.         random_shuffle(list_edge.begin() , list_edge.end());
  56.  
  57.         for (pair<int , int> p : list_edge) {
  58.                 cout << p.first << ' ' << p.second;
  59.                 if (stW != nuLL) cout << ' ' << rand(stW , enW) << '\n'; else cout << '\n';
  60.         }
  61. }
  62.  
  63. void rand_tree_perfect(int n , long long stW = nuLL , long long enW = nuLL) {
  64.         for (int i = 2 ; i <= n ; i++) {
  65.                 bool R = rand(false , true);
  66.                 if (R == true) list_edge.push_back(make_pair(i / 2 , i));
  67.                 else list_edge.push_back(make_pair(i , i / 2));
  68.         }
  69.  
  70.         random_shuffle(list_edge.begin() , list_edge.end());
  71.  
  72.         for (pair<int , int> p : list_edge) {
  73.                 cout << p.first << ' ' << p.second;
  74.                 if (stW != nuLL) cout << ' ' << rand(stW , enW) << '\n'; else cout << '\n';
  75.         }
  76. }
  77.  
  78. vector<int> list_int;
  79.  
  80. void rand_tree_line(int n , long long stW = nuLL , long long enW = nuLL) {
  81.         for (int i = 1 ; i <= n ; i++) list_int.push_back(i);
  82.  
  83.         random_shuffle(list_int.begin() , list_int.end());
  84.  
  85.         for (int i = 1 ; i < n ; i++) {
  86.                 bool R = rand(false , true);
  87.  
  88.                 if (R == true) cout << list_int[i - 1] << ' ' << list_int[i];
  89.                 else cout << list_int[i] << ' ' << list_int[i - 1];
  90.  
  91.                 if (stW != nuLL) cout << ' ' << rand(stW , enW) << '\n'; else cout << '\n';
  92.         }
  93. }
  94.  
  95. int32_t main() {
  96.         ios_base :: sync_with_stdio(false); 
  97.         cin.tie(0); cout.tie(0);
  98.  
  99.         srand(time(NULL));
  100.  
  101.         freopen("txt.inp" , "w" , stdout);
  102.  
  103.         return 0;
  104. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/jEtdVJ
language:
C++ (gcc 8.3)
created:
1 day 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!