Advertisement
ivnikkk

Untitled

Aug 2nd, 2022
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.94 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include "bits/stdc++.h"
  3. using namespace std;
  4. #define all(a) a.begin(), a.end()
  5.  
  6. vector<vector<int>> gr;
  7. vector<int> mpair;
  8. constexpr int N = 151;
  9. bitset<N> used_1, used_2, used_3;
  10.  
  11. bool try_kunh(int v) {
  12.     if (used_1[v]) return false;
  13.     used_1[v] = true;
  14.     for(int &u : gr[v]) {
  15.         if (mpair[u] < 0 || try_kunh(mpair[u])) {
  16.             mpair[u] = v;
  17.             return true;
  18.         }
  19.     }
  20.     return false;
  21. }
  22.  
  23. void dfs(int v, bool indef) {
  24.     if (indef) {
  25.         used_1[v] = 1;
  26.         indef ^= 1;
  27.         for(int &u : gr[v]) {
  28.             if (!used_2[u]) {
  29.                 dfs(u, indef);
  30.             }
  31.         }
  32.         return;
  33.     }
  34.     used_2[v] = 1;
  35.     indef ^= 1;
  36.     if (mpair[v] != -1 && !used_1[mpair[v]]) {
  37.         dfs(mpair[v], indef);
  38.     }
  39. }
  40. signed main() {
  41. #ifdef _DEBUG
  42.     freopen("input.txt", "r", stdin);
  43.     freopen("output.txt", "w", stdout);
  44. #endif
  45.     ios_base::sync_with_stdio(false);
  46.     cin.tie(nullptr);
  47.     cout.tie(nullptr);
  48.     int t = 1;
  49.     cin >> t;
  50.     while (t--) {
  51.         gr.clear(); mpair.clear();
  52.         used_1 = 0; used_2 = 0;
  53.         int n, m;
  54.         cin >> n >> m;
  55.         gr.resize(n);
  56.         for (int i = 0; i < n; i++) {
  57.             bitset<N> push = 0;
  58.             int v;
  59.             while (cin >> v) {
  60.                 if (v == 0) break;
  61.                 else push[v - 1] = 1;
  62.             }
  63.             for (int j = 0; j < m; j++) if (!push[j]) gr[i].push_back(j);
  64.         }
  65.         mpair.resize(m, -1);
  66.         used_1 = 0, used_2 = 0, used_3 = 0;
  67.         for (int i = 0; i < n; i++) if (try_kunh(i)) used_1 = 0;
  68.         for (int i = 0; i < m; i++) if (mpair[i] != -1) used_3[mpair[i]] = 1;
  69.         used_1 = 0; used_2 = 0;
  70.         for (int i = 0; i < n; i++) if (!used_3[i]) dfs(i, 1);
  71.         vector<int> ans1, ans2;
  72.         for (int i = 0; i < n; i++) if (used_1[i]) ans1.push_back(i + 1);
  73.         for (int i = 0; i < m; i++) if (!used_2[i]) ans2.push_back(i + 1);
  74.         cout << (int)ans1.size() + (int)ans2.size() << '\n';
  75.         cout << (int)ans1.size() << ' ' << (int)ans2.size() << '\n';
  76.         for (int &res : ans1) {
  77.             cout << res << ' ';
  78.         }
  79.         cout << '\n';
  80.         for (int &res : ans2) {
  81.             cout << res << ' ';
  82.         }
  83.         cout << '\n';
  84.     }
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement