看起来是代码的某一处细节错了,但是找不到(x
有好心人愿意提供一组数据吗。
#include <bits/stdc++.h>
using namespace std;
#define ios_fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ll long long
#define emp emplace_back
const int maxn = 20000 + 7;
int n, m, G[5001][5001], scctot, cnt[maxn], sum;
int dfn[maxn], low[maxn], dfnnum;
int stk[maxn], top, ins[maxn], id[maxn];
vector<vector<int>> e;
void tarjan(int x) {
dfn[x] = low[x] = ++dfnnum;
ins[x] = 1, stk[++top] = x;
for (int& v : e[x]) {
if (!dfn[v]) {
tarjan(v), low[x] = min(low[x], low[v]);
} else if (ins[v]) {
low[x] = min(low[x], dfn[v]);
}
}
if (low[x] == dfn[x]) {
++scctot;
for (int i = -1; i != x;) {
i = stk[top--];
ins[i] = false, id[i] = scctot;
}
}
}
void solve() {
cin >> n;
e.assign(2 * n + 1, {});
for (int i = 1, tm; i <= n; i++) {
cin >> tm;
for (int j = 1, k; j <= tm; j++) {
cin >> k, G[i][k] = 1;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) continue;
if (G[i][j]) {
e[i + n].emp(j); // 如果i不在团里面,j只能在团里面
} else {
e[i].emp(j + n); // 如果i在团里面,j不可以在团里面
}
}
}
for (int i = 1; i <= 2 * n; i++)
if (!dfn[i]) tarjan(i);
for (int i = 1; i <= n; i++)
if (id[i] == id[i + n]) {
cout << 0 << endl;
return;
}
int cnt0 = 0, cnt1 = 0; // 独立集, 团
#define state(x) (id[x] > id[x + n]) // 1表示独立集
for (int i = 1; i <= n; i++) {
state(i) ? cnt0++ : cnt1++;
}
for (int i = 1; i <= n; i++) {
if (state(i)) continue;
for (int j = 1; j <= n; j++) {
if (G[i][j]) cnt[j]++;
}
}
for (int i = 1; i <= n; i++)
if (cnt[i] == cnt1 - 1 && state(i)) sum++;
int ans = (cnt0 >= 1) && (cnt1 >= 1);
for (int i = 1; i <= n; i++) {
if (state(i)) continue;
int tmp = 0, pos = -1;
for (int j = 1; j <= n; j++) {
if ((state(j) == 1) && (G[i][j])) tmp++, pos = j;
}
if (tmp > 1) continue;
if (tmp == 1) {
ans += (pos > 0 && cnt[pos] == cnt1); // 只能交换
} else {
ans += cnt1 > 1; // 直接移过去
for (int j = 1; j <= n; j++)
if (state(j) && G[i][j]) {
if (cnt[j] == cnt1 - 1) sum--;
cnt[j]--;
if (cnt[j] == cnt1 - 1) sum++;
}
ans += sum; // 交换
for (int j = 1; j <= n; j++)
if (state(j) && G[i][j]) {
if (cnt[j] == cnt1 - 1) sum--;
cnt[j]++;
if (cnt[j] == cnt1 - 1) sum++;
}
}
}
cout << ans << endl;
}
int main() {
ios_fast;
int TEST = 1;
while (TEST--) solve();
}
/*
*/