94pts 求调,玄关!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
const int N = 2e5 + 5;
int n, m;
vector <int> G[N];
int deg[N];
bool use[N];
set <pii> s;
vector <int> pg; // Point_Group
int cnt, ans = 1;
void EX_Topological_sorting(void) {
for (int i = 1; i <= n; ++i) {
s.insert(make_pair(deg[i], i));
}
while (s.size() && s.begin() -> first != (--s.end()) -> first) {
int u = s.begin() -> second;
s.erase(s.begin());
use[u] = true;
for (int v : G[u]) {
if (use[v]) continue;
s.erase(make_pair(deg[v], v));
--deg[v];
s.insert(make_pair(deg[v], v));
}
}
for (auto x : s) {
pg.emplace_back(x.second);
//printf("%d ", x.second);
}
return ;
}
int main(void) {
//freopen("clique.in", "r", stdin);
//freopen("clique.out", "w", stdout);
scanf("%d", &n);
for (int u = 1, ki; u <= n; ++u) {
scanf("%d", &ki);
for (int j = 1, v; j <= ki; ++j) {
scanf("%d", &v);
G[u].push_back(v);
++deg[v];
}
}
EX_Topological_sorting(); // ex拓扑排序
if (deg[pg[0]] + 1 != pg.size()) {
printf("0");
return 0;
}
for (int u = 1; u <= n; ++u) {
for (int v : G[u]) {
if (use[u] && use[v]) {
printf("0");
return 0;
}
}
}
for (int i = 1; i <= n; ++i) {
deg[i] = G[i].size();
}
for (int u : pg) {
bool flag = true;
for (int v : G[u]) {
if (use[v]) {
flag = false;
break;
}
}
if (flag) {
++ans;
for (int v = 1; v <= n; ++v) {
if (use[v] && v != u && deg[v] == pg.size() - 1) {
++ans;
}
}
}
}
printf("%d", ans);
return 0;
}