看了别人的题解。须要用到匈牙利算法的强连通算法
#include#include #include #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 eg[MAXN];vector 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;}