Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <unordered_map>
- using namespace std;
- vector<int> temp;
- int num1 = 0;
- int num2 = 0;
- int n, a, b;
- int m;
- int ans = 0;
- unordered_map<int, int> u_m1, u_m2;
- void color(int v, int now_c, vector<vector<int>> &g2) {
- temp[v] = now_c;
- for (auto u : g2[v]) {
- if (temp[u] == 0) {
- if (now_c == 1) {
- color(u, 2, g2);
- } else {
- color(u, 1, g2);
- }
- }
- }
- }
- int deep(int v, vector<bool> &used, vector<vector<int>> &g, vector<int> &vec) {
- if (used[v] == 1)
- return 0;
- used[v] = 1;
- for (size_t i = 0; i < g[v].size(); ++i) {
- if ((vec[g[v][i]] + 1) == 0 || deep(vec[g[v][i]], used, g, vec)) {
- vec[g[v][i]] = v;
- return 1;
- }
- }
- return 0;
- }
- int main() {
- vector<int> vec(20000, -1);
- cin >> n;
- vector<vector<int>> g2(n);
- temp.assign(n, 0);
- for (int i = 0; i < n; ++i) {
- cin >> a;
- for (int j = 0; j < a; j++) {
- cin >> b;
- g2[i].push_back(b);
- }
- }
- for (int i = 0; i < n; ++i)
- if (temp[i] == 0)
- color(i, 1, g2);
- for (int i = 0; i < n; ++i)
- if (temp[i] == 1)
- u_m1[i] = num1++;
- else
- u_m2[i] = num2++;
- vector<vector<int>> g(num1);
- for (size_t i = 0; i < n; ++i)
- for (size_t j = 0; j < g2[i].size(); ++j)
- g[u_m1[i]].push_back(u_m2[g2[i][j]]);
- vector<bool> used(num1, 0);
- for (int i = 0; i < num1; ++i) {
- used.assign(num1, 0);
- if (deep(i, used, g, vec))
- ++ans;
- }
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement