Advertisement
Guest User

Untitled

a guest
Oct 15th, 2019
128
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.70 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4.  
  5. using namespace std;
  6.  
  7. vector<int> temp;
  8. int num1 = 0;
  9. int num2 = 0;
  10. int n, a, b;
  11. int m;
  12. int ans = 0;
  13. unordered_map<int, int> u_m1, u_m2;
  14.  
  15. void color(int v, int now_c, vector<vector<int>> &g2) {
  16.     temp[v] = now_c;
  17.     for (auto u : g2[v]) {
  18.         if (temp[u] == 0) {
  19.             if (now_c == 1) {
  20.                 color(u, 2, g2);
  21.             } else {
  22.                 color(u, 1, g2);
  23.             }
  24.         }
  25.     }
  26. }
  27.  
  28.  
  29. int deep(int v, vector<bool> &used, vector<vector<int>> &g, vector<int> &vec) {
  30.     if (used[v] == 1)
  31.         return 0;
  32.     used[v] = 1;
  33.     for (size_t i = 0; i < g[v].size(); ++i) {
  34.         if ((vec[g[v][i]] + 1) == 0 || deep(vec[g[v][i]], used, g, vec)) {
  35.             vec[g[v][i]] = v;
  36.             return 1;
  37.         }
  38.     }
  39.     return 0;
  40. }
  41.  
  42.  
  43. int main() {
  44.     vector<int> vec(20000, -1);
  45.     cin >> n;
  46.     vector<vector<int>> g2(n);
  47.     temp.assign(n, 0);
  48.     for (int i = 0; i < n; ++i) {
  49.         cin >> a;
  50.         for (int j = 0; j < a; j++) {
  51.             cin >> b;
  52.             g2[i].push_back(b);
  53.         }
  54.     }
  55.     for (int i = 0; i < n; ++i)
  56.         if (temp[i] == 0)
  57.             color(i, 1, g2);
  58.     for (int i = 0; i < n; ++i)
  59.         if (temp[i] == 1)
  60.             u_m1[i] = num1++;
  61.         else
  62.             u_m2[i] = num2++;
  63.     vector<vector<int>> g(num1);
  64.     for (size_t i = 0; i < n; ++i)
  65.         for (size_t j = 0; j < g2[i].size(); ++j)
  66.             g[u_m1[i]].push_back(u_m2[g2[i][j]]);
  67.     vector<bool> used(num1, 0);
  68.     for (int i = 0; i < num1; ++i) {
  69.         used.assign(num1, 0);
  70.         if (deep(i, used, g, vec))
  71.             ++ans;
  72.     }
  73.     cout << ans;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement