Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <vector>
- #include <queue>
- #include <algorithm>
- #include <string>
- #include <stack>
- #include <set>
- #include <map>
- #define pii pair <int, int>
- #define pb(x) push_back(x)
- using namespace std;
- using ll = long long;
- using ld = long double;
- using db = double;
- void cv(vector <int> &v) {
- for (auto x : v) cout << x << ' ';
- cout << "\n";
- }
- void cvl(vector <ll> &v) {
- for (auto x : v) cout << x << ' ';
- cout << "\n";
- }
- void cvv(vector <vector <int> > &v) {
- for (auto x : v) cv(x);
- cout << "\n";
- }
- void cvb(vector <bool> v) {
- for (bool x : v) cout << x << ' ';
- cout << "\n";
- }
- void cvs(vector <string> v) {
- for (auto a : v) {
- cout << a << "\n";
- }
- }
- void cvp(vector <pii> a) {
- for (auto p : a) {
- cout << p.first << ' ' << p.second << "\n";
- }
- cout << "\n";
- }
- bool sh;
- int n, k;
- vector <vector <int> > G;
- bool in_it(vector <int> a, vector <int> b) {//a inside b
- if (a.size() > b.size()) {
- return 0;
- }
- for (int i: a) {
- if (find(b.begin(), b.end(), i) == b.end()) {
- return 0;
- }
- }
- return 1;
- }
- vector <bool> in, out, was;
- void dfs(int v) {
- was[v] = 1;
- for (int u: G[v]) {
- if (in[u]) {
- continue;
- }
- in[u] = 1;
- out[v] = 1;
- if (was[u]) {
- continue;
- }
- dfs(u);
- }
- }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cin >> n >> k;
- G.resize(n);
- sh=0;
- vector <vector <int> > ing(n);
- for (int i = 0; i < n; ++i) {
- int m; cin >> m;
- for (int j = 0; j < m; ++j) {
- int x; cin >> x;
- ing[i].pb(x);
- }
- sort(ing[i].begin(), ing[i].end());
- }
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n && j != i; ++j) {
- if (in_it(ing[i], ing[j])) {
- G[i].pb(j);
- if (sh) {
- cout << i << " in " << j << "\n";
- }
- }
- if (in_it(ing[j], ing[i])) {
- G[j].pb(i);
- if (sh) {
- cout << j << " in " << i << "\n";
- }
- }
- }
- }
- in.assign(n, 0);
- out.assign(n, 0);
- was.assign(n, 0);
- for (int i = 0; i < n; ++i) {
- if (in[i]) {
- continue;
- }
- dfs(i);
- }
- int ans = 0;
- for (int i = 0; i < n; ++i) {
- if (!out[i]) {
- ans++;
- }
- }
- cout << ans;
- if (sh) {
- cout << "G\n";
- for (int i = 0; i < n; ++i) {
- cout << i << ": ";
- for (int j: G[i]) {
- cout << j << ' ';
- } cout << "\n";
- } cout << "\n";
- cout << "ing\n";
- cvv(ing);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement