因为HDU暂时关闭了，在这里暂存代码和思路。
更新：已通过
题面
题意
给定 n 个王子 和 
个公主，然后输入n行，每一行第一个数字k代表 第 i 个王子喜欢公主的数量，随后的k个数字就是这个王子喜欢公主的编号。假设已经有最大匹配 x ，要求不影响这个最大匹配数量，输出每个王子可以迎娶的公主编号。
思路
正常建有向图，跑一遍最大匹配，用 boys 和 girl 数组记录那个王子对应哪个公主，然后对于王子没有匹配上公主的情况，建立虚拟点(公主) ，把这个王子跟这个虚拟点连条边，同时将所有王子都像这个虚拟点连边。反之亦然，建立虚拟点(王子) ，把虚拟点跟所有公主连一条边。
然后建立反向边，将所有公主跟girl数组所对应的王子连边 ， 同时将所有公主也跟虚拟点连边。跑TarJan获得一棵缩了点的树，对于每个王子，遍历所喜欢的公主，将虚拟点去除掉并且满足属于同一个环里就加进答案里，排序输出即可。
代码实现
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sc(x) scanf("%d",&x)
#define _sc(x) scanf("%lld",&x)
#define pf(x) printf("%d",x);
#define _pf(x) printf("%lld",x);
#define FOR(i,a,b) for(int i = a;i<=b;++i)
#define _FOR(i,a,b) for(int i = a;i<b;++i)
#define pb push_back
#define lb lowber_bound
#define ub upper_bound
#define lson(x) ((x) * 2)
#define rson(x) ((x) * 2 + 1)
const ll mod = 1e9+7;
const ll maxn = 2e6+10;
const double eps = 1e-6;
const int INF = INT_MAX;
ll pow2(ll a,ll n){ ll res = 1ll;while(n){if(n&1) res = (res*a)%mod;a = (a*a)%mod;n >>= 1;}return res;}
ll gcd(ll a,ll b){ return b?gcd(b,a%b):a; }
const int N = 2e3 + 5;
const int M = 2 * N * N;
int T;
int n,m,k;
struct Edge{
int to,next;
}e[M];
int head[N] , vis[N] , boy[N] , girl[N];
int dfn[N] , low[N] , stk[N] , belong[N] , instance[N];
int tot,timer,tp,scc;
vector<int> ans;
void init(){
memset(head,-1,sizeof(head));
memset(boy,0,sizeof(boy));
memset(girl,0,sizeof(girl));
memset(dfn,0,sizeof(dfn));
memset(belong,0,sizeof(belong));
memset(instance,0,sizeof(instance));
tot = timer = tp = scc = 0;
}
void add(int u,int v){
e[tot].to = v;
e[tot].next = head[u];
head[u] = tot++;
}
int dfs(int u){
for(int i = head[u];~i;i = e[i].next){
int v = e[i].to;
if(vis[v]) continue;
vis[v] = 1;
if(!girl[v] || dfs(girl[v])){
girl[v] = u;
boy[u] = v;
return 1;
}
}
return 0;
}
void tarjan(int u,int fa){
dfn[u] = low[u] = ++timer;
stk[++tp] = u; instance[u] = 1;
for(int i = head[u];~i;i = e[i].next){
int v = e[i].to;
if(!dfn[v]){
tarjan(v,u);
low[u] = min(low[u],low[v]);
// if(low[v] > dfn[u]){
//
// }
}else if(instance[v]){
low[u] = min(low[u],dfn[v]);
}
}
if(dfn[u] == low[u]){
int v;
++scc;
do{
v = stk[tp--];
belong[v] = scc;
instance[v] = 0;
}while(v != u);
}
}
void solve(){
sc(n); sc(m);
FOR(u,1,n){
int t; sc(t);
while(t--){
int v;
sc(v);
add(u,v + 500);
}
}
FOR(i,1,n){
memset(vis,0,sizeof(vis));
dfs(i);
}
int cnt = 0;
FOR(i,1,n){
if(!boy[i]){
++cnt;
int v = 1000 + cnt;
boy[i] = v;
girl[v] = i;
FOR(j,1,n) add(j,v);
}
}
FOR(i,501,500+m){
if(!girl[i]){
++cnt;
int v = 1000 + cnt;
boy[v] = i;
girl[i] = v;
FOR(j,501,500+m) add(v,j);
}
}
FOR(i,501 , 501 + m){
add(i,girl[i]);
}
FOR(i,501,1000+cnt) add(i,girl[i]);
FOR(i,1,n){
if(!dfn[i]){
tarjan(i,0);
}
}
printf("Case #%d:\n",++k);
FOR(i,1,n){
ans.clear();
for(int j = head[i];~j;j = e[j].next){
int v = e[j].to;
if(v < 500 || v > 1000) continue;
if(belong[i] == belong[v]){
ans.push_back(v - 500);
}
}
sort(ans.begin(),ans.end());
printf("%d",ans.size());
for(auto x:ans){
printf(" %d",x);
}
puts("");
}
}
int main(void){
sc(T);
while(T--){
init();
solve();
}
return 0;
}