背景：本来是在做Voj的连通分量，做到了E（ hdu_4685 ），想到了二分图，但是笔者只会最大匹配，但题目要求要输出所有的最大匹配情况，想了好久都没想出来怎么做，因为如果我已知一个最大匹配，那么就可以将公主连反向边指向王子，然后跑tarjan，将每个强连通分量的王子配公主输出即可，但是这题没有给出最大匹配，这个还不是最坑的，因为可以跑一次最大匹配，最坑的是n个王子，但是有m个公主，看到这个真的想打人，这个就真的难受了，因为如果有人单身怎么办？？所以就去百度了，然后题解几乎全部提及Poj1904，于是乎笔者就去找到了这题，这题就是笔者想的那个给出匹配的版本，所以很快A掉了，但是！！re了4发，因为王子公主就2000，笔者边集数组没有多想，只开了两倍，到最后一直开到10w都还是re，最后百度一看，20W起加（貌似有个204000）过的，最后数组开到26w就过去了，不得不说这题的这个坑点真的是，很难过了。
题目大意：给出n个王子和他们仰慕的公主，接下来给出每个公主已经匹配的王子（即给出一组最大匹配），输出每个王子最多能和哪些公主匹配。
题解：对于王子仰慕的公主建边，而题目提供的最大匹配，用于建反向边，然后tarjan缩点，同一个分量里面的王子公主随意输出（笔者排了个序方便差错，忘了题目是否有要求）。
PS：今天应该可以把hdu_4685写出来，题解说是要虚拟出公主和王子，容笔者仔细想想，感觉想通了实现应该很快，毕竟这些点都挺熟悉的。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int N = 5005;
const int M = 260000;
const int INF = 0x3f3f3f3f;
struct Edge
{
int u, v, nxt;
};
Edge edge[M];
int ecnt, head[N];
int top, sum, dep;
bool vis[N];
int sta[N], low[N], dfn[N], col[N];
int ans[N];
void _add( int a, int b )
{
edge[ecnt].u = a;
edge[ecnt].v = b;
edge[ecnt].nxt = head[a];
head[a] = ecnt ++;
}
void tarjan( int u )
{
sta[++top] = u;
low[u] = dfn[u] = ++dep;
vis[u] = 1;
for ( int i = head[u]; i+1; i = edge[i].nxt )
{
int v = edge[i].v;
if ( !dfn[v] )
{
tarjan(v);
low[u] = min( low[u], low[v] );
}
else if ( vis[v] )
low[u] = min( low[u], low[v] );
}
if ( low[u] == dfn[u] )
{
vis[u] = 0;
col[u] = ++sum;
while ( sta[top] != u )
{
vis[sta[top]] = 0;
col[sta[top--]] = sum;
}
top --;
}
}
int main()
{
int n;
scanf("%d", &n);
memset(head,-1,sizeof(head));
for ( int i = 1; i <= n; i ++ )
{
int cn, pricn;
scanf("%d", &cn);
while ( cn -- )
{
scanf("%d", &pricn);
_add( i, pricn + n );
}
}
for ( int i = 1; i <= n; i ++ )
{
int pric;
scanf("%d", &pric);
_add( pric + n, i );
}
for ( int i = 1; i <= n; i ++ )
if ( !dfn[i] )
tarjan(i);
for ( int i = 1; i <= n; i ++ )
{
int cnt = 0;
for ( int j = head[i]; j+1; j = edge[j].nxt )
{
int v = edge[j].v;
if ( col[i] == col[v] )
ans[cnt++] = v - n;
}
sort(ans,ans+cnt);
printf("%d", cnt);
for ( int i = 0; i < cnt; i ++ )
printf(" %d", ans[i]);
printf("\n");
}
return 0;
}