Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- vector<int> used;
- vector<int> r;
- vector<vector<int>> g;
- bool dfs(int v, int c)
- {
- if(used[v] == c)
- {
- return false;
- }
- used[v] = c;
- for(int i : g[v])
- {
- if(r[i] == -1)
- {
- r[i] = v;
- return true;
- }
- }
- for(int i : g[v])
- {
- if(dfs(r[i], c))
- {
- r[i] = v;
- return true;
- }
- }
- return false;
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- int n;
- cin >> n;
- r.resize(n * 2, -1);
- used.resize(n * 2);
- g.resize(n);
- set<set<string>> V;
- for(int i = 0; i < n; ++i)
- {
- int k;
- cin >> k;
- set<string> local;
- for(int j = 0; j < k; ++j)
- {
- string s1;
- cin >> s1;
- local.insert(s1);
- }
- V.insert(local);
- }
- vector<set<string>> v;
- for(auto i : V)
- {
- v.push_back(i);
- }
- for(int i = 0; i < v.size(); ++i)
- {
- for(int j = 0; j < v.size(); ++j)
- {
- if(i == j) continue;
- bool st = true;
- for(auto x : v[i])
- {
- if(v[j].find(x) == v[j].end())
- {
- st = false;
- break;
- }
- }
- if(st)
- {
- g[i].push_back(n + j);
- }
- }
- }
- int ans = 0;
- // for(int i = 0; i < n; ++i)
- // {
- // g[i].push_back(i + n);
- // }
- int c = 1;
- for(int i = 0; i < n; ++i)
- {
- if(dfs(i, c)) {
- ++ans;
- ++c;
- }
- }
- cout << v.size() - ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement