http://poj.org/problem?id=1904

Description

Input

Output

Sample Input

4

2 1 2

2 1 2

2 2 3

2 3 4

1 2 3 4

Sample Output

2 1 2

2 1 2

1 3

1 4

Hint

/**

poj1904 二分图匹配+强连通分量

题目大意：有n个王子和n个公主，每一个王子仅仅能和他喜欢的公主结婚，公主能够和随意王子结婚。如今知道，每一个王子的结婚对象（都有结婚对象），和每一个王子所喜欢的公主，问

           每一个王子能够和那些公主结婚，而且保证每一个王子都得有结婚对象

解题思路：每一个王子向他喜欢的公主连一条有向边，每一个公主向她的结婚对象连一条有向边，求取每一个王子所在的强连通分量，该王子可和他在同一个强连通分量里的公主结婚。满足

           条件。为什么呢？由于每一个王子仅仅能和喜欢的妹子结婚，初始完美匹配中的丈夫和妻子之间有两条方向不同的边能够互达，则同一个强连通分量中的王子数和妹子数一定是相等的，若王子x能够和另外的一个妹子a结婚，妹子a的原配王子y肯定能找到另外一个妹子b结婚，由于假设找不到的话，则x和a必不在同一个强连通分量中。

所以一个王子能够和全部与他同一强连通分量的妹子结婚，而这不会导致同一强连通分量中的其它王子找不到妹子结婚。

*/

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <iostream>

#include <stack>

using namespace std;

const int maxn=5005;

int head[maxn],ip;

void init()

{

    memset(head,-1,sizeof(head));

    ip=0;

}

struct note

{

    int v,next;

} edge[400005];

void addedge(int u,int v)

{

    edge[ip].v=v,edge[ip].next=head[u],head[u]=ip++;

}

int n,cnt[maxn];

int dfn[maxn],low[maxn],belong[maxn],index,cnt_tar,cont[maxn],instack[maxn*2];

stack<int>q;

void tarjan(int u)

{

    dfn[u]=low[u]=++index;

    q.push(u);

    instack[u]=1;

    for(int i=head[u]; i!=-1; i=edge[i].next)

    {

        int v=edge[i].v;

        if(!dfn[v])

        {

            tarjan(v);

            low[u]=min(low[u],low[v]);

        }

        else if(instack[v])

        {

            low[u]=min(low[u],dfn[v]);

        }

    }

    if(dfn[u]==low[u])

    {

        cnt_tar++;

        int j;

        do

        {

            j=q.top();

            q.pop();

            belong[j]=cnt_tar;

            instack[j]=0;

            cont[cnt_tar]++;

        }

        while(j!=u);

    }

}

void solve()

{

    index=0,cnt_tar=0;

    memset(dfn,0,sizeof(dfn));

    memset(low,0,sizeof(low));

    memset(instack,0,sizeof(instack));

    memset(cont,0,sizeof(cont));

    for(int i=1; i<=n; i++)

    {

        if(!dfn[i])

            tarjan(i);

    }

}

int main()

{

    while(~scanf("%d",&n))

    {

        init();

        for(int i=1; i<=n; i++)

        {

            int x,y;

            scanf("%d",&x);

            for(int j=0; j<x; j++)

            {

                scanf("%d",&y);

                addedge(i,y+n);

            }

        }

        for(int i=1; i<=n; i++)

        {

            int x;

            scanf("%d",&x);

            addedge(x+n,i);

        }

        solve();

        for(int u=1; u<=n; u++)

        {

            int k=0;

            for(int i=head[u]; i!=-1; i=edge[i].next)

            {

                int v=edge[i].v;

                if(belong[u]==belong[v])

                {

                    cnt[k++]=v-n;

                }

            }

            sort(cnt,cnt+k);

            printf("%d",k);

            for(int i=0; i<k; i++)

            {

                printf(" %d",cnt[i]);

            }

            printf("\n");

        }

    }

    return 0;

}