建图：王子u喜欢女孩v，则u到v连一条边。对于给出的初始完美匹配，王子u与女孩v匹配，则v到u连一条边。然后求SCC。
显然对于同一个SCC中王子数目和女孩数目是相等的，并且从某个王子出发能够到达所有女孩，这样，王子可以和属于同一个SCC中的任意一个女孩结婚，而不会影响其他王子。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
const int maxn = , INF = 0x7fffffff;
int pre[maxn], low[maxn], sccno[maxn], dfs_clock, scc_cnt, cnt;
int head[maxn];
vector<int> G[maxn];
stack<int> S;
int n, k;
struct node
{
int u, v, next;
}Node[maxn]; void add(int u, int v)
{
Node[cnt].u = u;
Node[cnt].v = v;
Node[cnt].next = head[u];
head[u] = cnt++;
} void dfs(int u)
{
pre[u] = low[u] = ++dfs_clock;
S.push(u);
for(int i=head[u]; i!=-; i=Node[i].next)
{
int v = Node[i].v;
if(!pre[v])
{
dfs(v);
low[u] = min(low[u], low[v]);
}
else if(!sccno[v])
low[u] = min(low[u], pre[v]);
}
if(low[u] == pre[u])
{
scc_cnt++;
for(;;)
{
int x = S.top(); S.pop();
sccno[x] = scc_cnt;
if(x == u) break;
}
}
} void init()
{
cnt = ;
mem(head, -);
mem(pre, );
mem(low, );
mem(sccno, );
} int main()
{
init();
scanf("%d",&n);
for(int i=; i<=n; i++)
{
scanf("%d",&k);
for(int j=; j<k; j++)
{
int v;
scanf("%d",&v);
add(i, n+v);
}
}
for(int i=; i<=n; i++)
{
int v;
scanf("%d",&v);
add(n+v, i);
}
for(int i=; i<=n; i++)
if(!pre[i])
dfs(i);
// cout<< 1211 <<endl;
for(int i=; i<=n; i++)
{
for(int j=head[i]; j!=-; j=Node[j].next)
{
if(sccno[i] == sccno[Node[j].v])
{
G[i].push_back(Node[j].v);
}
}
}
for(int i=; i<=n; i++)
sort(G[i].begin(), G[i].end());
for(int i=; i<=n; i++)
{
printf("%d ",G[i].size());
for(int j=; j<G[i].size(); j++)
printf("%d%s",G[i][j] - n,(j==G[i].size()-)?"\n":" ");
} return ;
}