fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <numeric>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. // Disjoint Set Union to find connected components
  9. struct DSU {
  10.     vector<int> parent;
  11.     DSU(int n) {
  12.         parent.resize(n + 1);
  13.         iota(parent.begin(), parent.end(), 0);
  14.     }
  15.     int find(int i) {
  16.         if (parent[i] == i)
  17.             return i;
  18.         return parent[i] = find(parent[i]);
  19.     }
  20.     void unite(int i, int j) {
  21.         int root_i = find(i);
  22.         int root_j = find(j);
  23.         if (root_i != root_j) {
  24.             parent[root_i] = root_j;
  25.         }
  26.     }
  27. };
  28.  
  29. void solve() {
  30.     int n;
  31.     cin >> n;
  32.     vector<int> a(n), b(n);
  33.     for (int i = 0; i < n; i++) cin >> a[i];
  34.     for (int i = 0; i < n; i++) cin >> b[i];
  35.  
  36.     vector<int> in(n + 1, 0), out(n + 1, 0);
  37.     vector<char> has_edge(n + 1, 0);
  38.     DSU dsu(n);
  39.  
  40.     // Build the graph degrees and components
  41.     for (int i = 0; i < n; i++) {
  42.         int u = a[i];
  43.         int v = b[i];
  44.         out[u]++;
  45.         in[v]++;
  46.         dsu.unite(u, v);
  47.         has_edge[u] = 1;
  48.         has_edge[v] = 1;
  49.     }
  50.  
  51.     // Calculate total imbalance jumps needed
  52.     long long d_total = 0;
  53.     for (int i = 1; i <= n; i++) {
  54.         if (out[i] > in[i]) {
  55.             d_total += out[i] - in[i];
  56.         }
  57.     }
  58.  
  59.     vector<char> is_root(n + 1, 0);
  60.     vector<char> is_balanced(n + 1, 1);
  61.  
  62.     // Analyze the components
  63.     for (int i = 1; i <= n; i++) {
  64.         if (has_edge[i]) {
  65.             int r = dsu.find(i);
  66.             is_root[r] = 1;
  67.             if (in[i] != out[i]) {
  68.                 is_balanced[r] = 0; // Component has a degree mismatch
  69.             }
  70.         }
  71.     }
  72.  
  73.     int comp = 0;
  74.     int bal = 0;
  75.     for (int i = 1; i <= n; i++) {
  76.         if (is_root[i]) {
  77.             comp++;
  78.             if (is_balanced[i]) {
  79.                 bal++;
  80.             }
  81.         }
  82.     }
  83.  
  84.     // Determine the minimum jumps required
  85.     int j = 0;
  86.     if (d_total > 0) {
  87.         j = d_total + bal;
  88.     } else {
  89.         if (comp == 1) {
  90.             j = 0;
  91.         } else {
  92.             j = comp;
  93.         }
  94.     }
  95.  
  96.     // Matches is Total Edges minus Jumps
  97.     cout << n - j << "\n";
  98. }
  99.  
  100. int main() {
  101.     // Fast I/O
  102.     ios_base::sync_with_stdio(false);
  103.     cin.tie(NULL);
  104.  
  105.     int t;
  106.     if (cin >> t) {
  107.         while (t--) {
  108.             solve();
  109.         }
  110.     }
  111.     return 0;
  112. }
Success #stdin #stdout 0s 5276KB
comments (?)
stdin
copy 
3
3
1 1 2
1 2 3
5
1 2 3 4 5
5 4 3 2 1
6
1 2 2 4 2 4
1 1 3 2 4 2
stdout
copy 
2
2
4
https://ideone.com/j9VZtN
language:
C++14 (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!