题目链接：
http://poj.org/problem?id=1904
题意：
有n个王子和n个公主，王子只能娶自己心仪的公主（一个王子可能会有多个心仪的公主），现已给出一个完美匹配，问每个王子都可以取哪些公主，并且保证取了一个公主后，全局还是存在完美匹配。
题解：
1、建图：
如果王子u对公主v心仪，则连一条边u->v。在样例给出的那组完美匹配中，如果王子u娶了公主v，连一条边v->u。
2、求强连通分量：
如果王子和自己心仪的公主属于同一个强连通分量，那么王子就可以娶这个公主。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stack>
#include<vector>
#include<cstring>
using namespace std; const int maxn=; int N; struct Edge{
int v,ne;
Edge(int v,int ne):v(v),ne(ne){}
Edge(){}
}egs[+maxn]; int head[maxn],tot; void addEdge(int u,int v){
egs[tot]=Edge(v,head[u]);
head[u]=tot++;
} int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
stack<int> S; 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%+'');
} void dfs(int u){
pre[u]=lowlink[u]=++dfs_clock;
S.push(u);
for(int i=head[u];i!=-;i=egs[i].ne){
Edge& e=egs[i];
int v=e.v;
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);
}
} void build(){
int cnt,v;
for(int i=;i<N;i++){
cnt=scan();
while(cnt--){
v=scan(); v--;
addEdge(i,v+N);
}
}
for(int i=;i<N;i++){
v=scan(); v--;
addEdge(v+N,i);
}
} void init(){
memset(head,-,sizeof(head));
tot=;
} int ans[],t; int main(){
while(scanf("%d",&N)==&&N){
init();
build();
find_scc(*N);
for(int i=;i<N;i++){
t=;
for(int j=head[i];j!=-;j=egs[j].ne){
Edge& e=egs[j];
int v=e.v;
if(sccno[i]==sccno[v]) ans[t++]=v;
}
sort(ans,ans+t);
out(t);
for(int i=;i<t;i++){
putchar(' ');
out(ans[i]+-N);
}
putchar('\n');
}
}
return ;
}