看了别人的题解。须要用到匈牙利算法的强连通算法
#include<cstdio>
#include<algorithm>
#include<vector>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const int MAXN = 1005;
int n, m;
int mb[MAXN], ma[MAXN];
bool vis[MAXN], gl[MAXN][MAXN];
vector<int> eg[MAXN];
vector<int> mmp[MAXN], res;
int dfs(int a)
{
for (int i = 0; i< eg[a].size(); ++i)
{
int v = eg[a][i];
if (!vis[v])
{
vis[v] = 1;
if (!mb[v] || dfs(mb[v]))
{
mb[v] = a;
ma[a] = v;
return 1;
}
}
}
return 0;
}
int hungary(int a)
{
int cnt = 0;
memset(mb, 0, sizeof mb);
for (int i = 1; i<= a; ++i)
{
memset(vis, 0, sizeof vis);
cnt += dfs(i);
}
return cnt;
}
int dfn[MAXN], low[MAXN], zu, belong[MAXN];
int nc;
int stk[MAXN], top, isinstk[MAXN];
void tarjan(int u)
{
dfn[u] = low[u] = nc++;
stk[top++] = u;
isinstk[u] = 1;
for (int i = 0; i< mmp[u].size(); ++i)
{
int v = mmp[u][i];
if (dfn[v] == -1)
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (isinstk[v] && low[u] > dfn[v])
{
low[u] = dfn[v];
}
}
if (dfn[u] == low[u])
{
int v;
do
{
v = stk[--top];
isinstk[v] = 0;
belong[v] = zu;
}while( v != u);
zu++;
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
int t;
scanf("%d", &t);
for (int o = 1; o<= t; ++o)
{
printf("Case #%d:\n", o);
scanf("%d%d", &n, &m);
for (int i = 1; i<= n; ++i)
{
int k, a;
scanf("%d", &k);
eg[i].clear();
while (k--)
{
scanf("%d", &a);
eg[i].push_back(a);
}
}
int cna = hungary(n);
cna = n+m-cna;
for (int i=n+1; i<= cna; ++i)
{
eg[i].clear();
for (int j = 1; j<= cna; ++j)
{
eg[i].push_back(j);
}
}
for (int i=m+1; i<= cna; ++i)
{
for (int j = 1; j<= n; ++j)
{
eg[j].push_back(i);
}
}
int nmc = hungary(cna);
for (int i = 1; i<= cna; ++i) mmp[i].clear();
for (int i = 1; i<= cna; ++i)
{
int a = mb[i];
for (int j = 0; j< eg[a].size(); ++j)
{
int v = eg[a][j];
if (v == i) continue;
mmp[i].push_back(v);
}
}
nc = 1;
memset(dfn, -1, sizeof dfn);
memset(low, -1, sizeof low);
top = 0;
zu = 0;
for (int i = 1; i<= cna; ++i)
{
if (dfn[i] == -1)
tarjan(i);
}
memset(gl, 0, sizeof gl);
for (int i = 1; i<= cna; ++i)
{
for (int j = 0; j< eg[i].size(); ++j)
{
gl[i][eg[i][j]] = 1;
}
}
for (int i = 1; i<= n; ++i)
{
res.clear();
for (int j = 1; j<= m; ++j)
{
if (gl[i][j] && belong[j] == belong[ma[i]])
res.push_back(j);
}
int sz = res.size();
printf("%d", sz);
for (int j = 0; j< sz; ++j)
{
printf(" %d", res[j]);
}
puts("");
}
}
return 0;
}