题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4685
题解：
这一题是poj 1904的加强版，poj 1904王子和公主的人数是一样多的，并且给出了一个完美匹配，而这一题王子和公主的人数是不同的，而且没有给出任何匹配。因此借鉴1904的做法，我们可以对这题做一些预处理，从而使得它和poj 1904一样能够用强连通分量来求解。
首先求出一个最大匹配，对于每一个没有匹配的王子，加一个虚拟的公主与之匹配，对于每一个没有匹配的公主，加一个虚拟的的王子与之匹配，这样就可以得到一个完美匹配了。并且使得所有的王子都与虚拟的公主连边，所有的公主都与每一个虚拟的王子相连
这样建完图后就可以和poj 1904一样的做法了。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std; const int maxn = ; int scan() {
int ret = , flag = ; char ch;
if ((ch = getchar()) == '-') flag = ;
else if (ch >= ''&&ch <= '') ret = ch - '';
while ((ch = getchar()) >= ''&&ch <= '') ret = ret * + ch - '';
return flag ? -ret : ret;
} void out(int x) {
if (x>) out(x / );
putchar(x % + '');
} int _t[maxn], lef[maxn]; int n, m; vector<int> G[maxn],G2[maxn]; //二分图的最大匹配-----------------------------------------------
bool match(int u) {
for (int i = ; i < G[u].size(); i++) {
int v = G[u][i];
if (!_t[v]) {
_t[v] = ;
if (lef[v]==- || match(lef[v])) {
lef[v] = u;
return true;
}
}
}
return false;
} void BM() {
for (int i = ; i < n; i++) {
memset(_t, , sizeof(_t));
match(i);
}
//for (int i = 0; i < m; i++) {
// printf("lef[%d]:%d\n", i + 1, lef[i]+1);
//}
}
//--------------------------------------------------------------- //tarjan求强连通----------------------------------------------
int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, scc_cnt;
stack<int> S; void dfs(int u) {
pre[u] = lowlink[u] = ++dfs_clock;
S.push(u);
for (int i = ; i < G2[u].size(); i++) {
int v = G2[u][i];
if (!pre[v]) {
dfs(v);
lowlink[u] = min(lowlink[u], lowlink[v]);
}
else if (!sccno[v]) {
lowlink[u] = min(lowlink[u], pre[v]);
}
}
if (lowlink[u] == pre[u]) {
scc_cnt++;
for (;;) {
int x = S.top(); S.pop();
sccno[x] = scc_cnt;
if (x == u) break;
}
}
} void find_scc(int n) {
dfs_clock = scc_cnt = ;
memset(sccno, , sizeof(sccno));
memset(pre, , sizeof(pre));
for (int i = ; i < n; i++) {
if (!pre[i]) dfs(i);
}
}
//--------------------------------------------------------------- int vis[maxn];
void solve() {
//build
memset(vis, , sizeof(vis));
int tot_n = n;
//构造完美匹配-----------------------
for (int i = ; i < m; i++) {
if (lef[i] == -) {
lef[i] = tot_n++;
}
vis[lef[i]] = ;
}
int tot_m = m;
for (int i = ; i < tot_n; i++) {
if (vis[i] == ) lef[tot_m++] = i;
}
//------------------- //每一个王子心仪的公主的连边
for (int i = ; i < n; i++) {
for (int j = ; j < G[i].size(); j++) {
int v = G[i][j];
G2[i].push_back(v + tot_n);
}
}
//每一个虚拟的王子与所有的公主的连边
for (int i = n; i < tot_n; i++) {
for (int v = ; v < m; v++) {
G2[i].push_back(v + tot_n);
}
}
//所有的王子与每一个虚拟公主连边
for (int i = m; i < tot_n; i++) {
for (int v = ; v < tot_n; v++) {
G2[v].push_back(i+tot_n);
}
}
//每一个公主与和她匹配的那个王子连边
for (int i = ; i < tot_n; i++) {
G2[i + tot_n].push_back(lef[i]);
} //printf("tot_n:%d\n", tot_n);
//for (int i = 0; i < tot_n * 2; i++) {
// printf("%d:", i + 1);
// for (int j = 0; j < G2[i].size(); j++) {
// int v = G2[i][j]; v++;
// printf("%d ", v);
// }
// printf("\n");
//} //solve
find_scc(tot_n*); //for (int i = 0; i < tot_n * 2; i++) {
// printf("sccno[%d]:%d\n", i + 1, sccno[i]);
for (int i = ; i < n; i++) {
vector<int> ans;
for (int j = ; j < G[i].size(); j++) {
int v = G[i][j];
if (sccno[i] == sccno[v + tot_n]) ans.push_back(v);
}
sort(ans.begin(), ans.end());
out(ans.size());
for (int i = ; i < ans.size(); i++) {
putchar(' ');
out(ans[i] + );
}
putchar('\n');
}
} void init() {
for (int i = ; i < maxn; i++) G[i].clear(),G2[i].clear();
memset(lef, -, sizeof(lef));
} int main() {
int tc,kase=;
tc = scan();
while (tc--) {
init();
n = scan(); m = scan();
int ct,v;
for (int i = ; i < n; i++) {
ct = scan();
for (int j = ; j < ct; j++) {
v = scan(); v--;
G[i].push_back(v);
}
}
printf("Case #%d:\n", ++kase);
BM();
solve();
}
return ;
}