Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include "bits/stdc++.h"
- using namespace std;
- #define all(a) a.begin(), a.end()
- vector<vector<int>> gr;
- vector<int> mpair;
- constexpr int N = 151;
- bitset<N> used_1, used_2, used_3;
- bool try_kunh(int v) {
- if (used_1[v]) return false;
- used_1[v] = true;
- for(int &u : gr[v]) {
- if (mpair[u] < 0 || try_kunh(mpair[u])) {
- mpair[u] = v;
- return true;
- }
- }
- return false;
- }
- void dfs(int v, bool indef) {
- if (indef) {
- used_1[v] = 1;
- indef ^= 1;
- for(int &u : gr[v]) {
- if (!used_2[u]) {
- dfs(u, indef);
- }
- }
- return;
- }
- used_2[v] = 1;
- indef ^= 1;
- if (mpair[v] != -1 && !used_1[mpair[v]]) {
- dfs(mpair[v], indef);
- }
- }
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int t = 1;
- cin >> t;
- while (t--) {
- gr.clear(); mpair.clear();
- used_1 = 0; used_2 = 0;
- int n, m;
- cin >> n >> m;
- gr.resize(n);
- for (int i = 0; i < n; i++) {
- bitset<N> push = 0;
- int v;
- while (cin >> v) {
- if (v == 0) break;
- else push[v - 1] = 1;
- }
- for (int j = 0; j < m; j++) if (!push[j]) gr[i].push_back(j);
- }
- mpair.resize(m, -1);
- used_1 = 0, used_2 = 0, used_3 = 0;
- for (int i = 0; i < n; i++) if (try_kunh(i)) used_1 = 0;
- for (int i = 0; i < m; i++) if (mpair[i] != -1) used_3[mpair[i]] = 1;
- used_1 = 0; used_2 = 0;
- for (int i = 0; i < n; i++) if (!used_3[i]) dfs(i, 1);
- vector<int> ans1, ans2;
- for (int i = 0; i < n; i++) if (used_1[i]) ans1.push_back(i + 1);
- for (int i = 0; i < m; i++) if (!used_2[i]) ans2.push_back(i + 1);
- cout << (int)ans1.size() + (int)ans2.size() << '\n';
- cout << (int)ans1.size() << ' ' << (int)ans2.size() << '\n';
- for (int &res : ans1) {
- cout << res << ' ';
- }
- cout << '\n';
- for (int &res : ans2) {
- cout << res << ' ';
- }
- cout << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement