fork download
copy 
  1. /*
  2. * Author: Geeza
  3. */
  4.  
  5. #include <bits/stdc++.h>
  6.  
  7. #define ld long double
  8. #define ll long long
  9. #define pb push_back
  10. #define fin(a, n) for(int i = a; i < n; i++)
  11. #define fjn(a, n) for(int j = a; j < n; j++)
  12. #define all(a) a.begin(),a.end()
  13. #define allr(a) a.rbegin(),a.rend()
  14. #define FAST ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
  15.  
  16. using namespace std;
  17.  
  18. const double PI = acos(-1);
  19. const int N = 1e5+20;
  20. const ll oo = 0x3f3f3f3f3f3f3f3f;
  21. const int MOD = 1000000007, inf = 1e6;
  22.  
  23. string di[] = {"D","L", "U", "R", "UL", "UR", "DL", "DR"};
  24. int dx[] = {+1, +0, +0, -1, -1, -1, +1, +1};
  25. int dy[] = {+0, -1, +1, +0, -1, +1, -1, +1};
  26. char dc[] = {'D', 'L', 'R', 'U'};
  27.  
  28. struct DSU {
  29.     vector<int> parent, size;
  30.     ll tot;
  31.     DSU(int n) : parent(n + 1), size(n + 1, 1) {
  32.         iota(parent.begin(), parent.end(), 0);
  33.         tot = n;
  34.     }
  35.  
  36.     int find(int x) {
  37.         if (x == parent[x]) return x;
  38.         return parent[x] = find(parent[x]);
  39.     }
  40.  
  41.     bool unite(int x, int y) {
  42.         x = find(x);
  43.         y = find(y);
  44.         if (x == y) return false;
  45.         if (size[x] < size[y]) swap(x, y);
  46.         tot--;
  47.         parent[y] = x;
  48.         size[x] += size[y];
  49.         return true;
  50.     }
  51. };
  52.  
  53. void solve() {
  54.     ll n, m1, m2; cin >> n >> m1 >> m2;
  55.     ll mx = max(m1, m2);
  56.     if (mx == n-1) return void(cout << "0\n");
  57.  
  58.     DSU dsu1(n), dsu2(n);
  59.  
  60.     fin(0, m1) {
  61.         ll u, v; cin >> u >> v;
  62.         dsu1.unite(u, v);
  63.     }
  64.  
  65.     fin(0, m2) {
  66.         ll u, v; cin >> u >> v;
  67.         dsu2.unite(u, v);
  68.     }
  69.  
  70.     ll needed = n-1-mx;
  71.     vector<pair<ll, ll>> ans;
  72.     for (ll i = 1; i <= n; i++) {
  73.         bool finish = false;
  74.         for (ll j = 1; j <= n; j++) {
  75.             if (dsu1.tot == 1) {
  76.                 finish = true;
  77.                 break;
  78.             }
  79.             bool can1 = dsu1.find(i) != dsu1.find(j);
  80.             bool can2 = dsu2.find(i) != dsu2.find(j);
  81.             if (can1 && can2) {
  82.                 ans.push_back({i, j});
  83.                 dsu1.unite(i, j);
  84.                 dsu2.unite(i, j);
  85.             }
  86.         }
  87.         if (finish) break;
  88.     }
  89.     cout << needed << "\n";
  90.     for (auto [u, v] : ans) {
  91.         cout << u << " " << v << "\n";
  92.     }
  93. }
  94.  
  95. int main() {
  96.     FAST;
  97. #ifndef ONLINE_JUDGE
  98.     freopen("input.txt","r",stdin);
  99.     freopen("output.txt","w",stdout);
  100. #endif
  101.     int tt = 1; //cin >> tt;
  102.     while(tt--){
  103.         solve();
  104.     }
  105.     return 0;
  106. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/WDcvaP
language:
C++ (gcc 8.3)
created:
19 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!