这个题目是看解题报告做的，最大感觉 是模型转化的奇妙。
如果prince i matches princess i',j matches j' oringinally, now i matches j' is acceptable, what about j?
else matches i' or k', then what about k? and so on.
The answer is they are in a strongly connected component! Fantastic!
#include <iostream>
#include <algorithm>
#define N 2007
using namespace std;
int love[N][N],m[N][N]={
0},ttm[N][N]={
0};
int n;
int girlLoveBoy[N];
int stk[N],top;
int colorBoy[N]={
0};
int label[N]={
0};
int mark;
void dfsa (int u);
void dfsb(int u);
void scc();
void input();
void output();
int main()
{
input();
scc();
output();
}
void input()
{
int i,j,k;
scanf("%d",&n);
for (i=1; i<=n; ++i)
{
scanf("%d",&love[i][0]);
for (k=1; k<=love[i][0]; ++k)
{
scanf("%d",&love[i][k]);
}
}
for (i=1; i<=n; ++i)
{
scanf("%d",&j);
girlLoveBoy[j] = i;
}
for (i=1; i<=n; ++i)
for (j=1; j<=love[i][0]; ++j)
{
k = girlLoveBoy[love[i][j]];
++m[i][0];
m[i][m[i][0]] = k;
++ttm[k][0];
ttm[k][ttm[k][0]] = i;
}
}
void dfsa(int u)
{
colorBoy[u] = -1;
for (int j =1; j<=m[u][0]; ++j)
if (colorBoy[m[u][j]] == 0)
dfsa(m[u][j]);
stk[top++] = u;
}
void dfsb(int u)
{
colorBoy[u] = -1;
label[u] = mark;
for (int j =1; j<=ttm[u][0]; ++j)
if (colorBoy[ttm[u][j]] == 0)
dfsb(ttm[u][j]);
}
void output()
{
int i,j,k;
for (i=1; i<=n; ++i)
{
top = 0;
for (j = 1; j<= love[i][0]; ++j)
{
k = girlLoveBoy[love[i][j]];
if (label[k] == label[i])
{
stk[top++] = love[i][j];
}
}
sort (stk,stk+top);
printf("%d",top);
for (j=0; j<top; ++j) printf(" %d",stk[j]);
printf("/n");
}
}
void scc()
{
int i;
for (i=1; i<=n; ++i)
if (colorBoy[i] == 0)
dfsa(i);
memset(colorBoy,0,sizeof(colorBoy));
mark = 1;
while (top>0)
{
if (colorBoy[stk[top-1]] == 0)
{
dfsb(stk[top-1]);
++mark;
}
--top;
}
}续：此题最终为求SCC，类似的问题有 http://acm.pku.edu.cn/JudgeOnline/problem?id=2186Popular Cows,及2－sat问题，最小树形图中找圈的方法也有些类似。