2022-02-09

题目描述

原题

Once upon a time there lived a king and he had N sons. And there were N beautiful girls in the kingdom and the king knew about each of his sons which of those girls he did like. The sons of the king were young and light-headed, so it was possible for one son to like several girls.

So the king asked his wizard to find for each of his sons the girl he liked, so that he could marry her. And the king's wizard did it -- for each son the girl that he could marry was chosen, so that he liked this girl and, of course, each beautiful girl had to marry only one of the king's sons.

However, the king looked at the list and said: "I like the list you have made, but I am not completely satisfied. For each son I would like to know all the girls that he can marry. Of course, after he marries any of those girls, for each other son you must still be able to choose the girl he likes to marry."

The problem the king wanted the wizard to solve had become too hard for him. You must save wizard's head by solving this problem.

中文

有n个王子和n个女孩，每个王子可能喜欢多个女孩。

先给出一个初始的完备匹配，问每个王子可以选择哪些女孩，

即无论王子选择这些女孩中的哪一个，使得剩下的王子仍能够选择喜欢的女孩。

输入格式

输入的第一行包含N 国王的儿子数（1≤ N≤ 20002000）。 接下来每个国王的儿子的N行包含他喜欢的女孩的名单：第一个K_i 他喜欢的女孩的数量，然后有K_i?个不同的整数，从1到N表示女孩的编号。

所有K_i?的总和不超过200000。

输入的最后一行是巫师所做的清单 N个不同的整数：对于每个儿子，给出他将按照此列表结婚的女孩的编号。

保证这个清单是正确的，也就是说，每个儿子都喜欢这个清单里面他所要结婚的女孩。

输出格式

输出N行。对于每个国王的儿子，首先打印L_i 他喜欢和可以结婚的不同女孩的数量。 在那之后，输出L_i?个不同的整数表示那些女孩的编号，按升序排列。

数据范围

见输入格式

样例 输入

4
2 1 2
2 1 2
2 2 3
2 3 4
1 2 3 4

输出

2 1 2
2 1 2
1 3
1 4

算法: 

　　tarjan     强连通分量

预备知识(大佬略)

• tarjan板子题

正片 

　　1. 这很明显是一个二分图,我们可以将代表王子的节点与他love的公主相连

　　　　然后将每个女孩连边到在初始匹配当中的王子的节点。

　　2.然后求出其强连通分量,我们可以发现每个王子所在的强连通分量里的女孩

　　　　就是该王子所可以选择的女孩。

　　A trick:王子的编号可以从1~N,公主编号可以从N+1~2*N

C++代码

#include
#include
#include
#include
#include
using namespace std;
const int N=4e3+10,M=N*N/2*2;
int h[N],ne[M],e[M],idx=1;
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
} 
int dfn[N],low[N],cnt,dep;
int n,m;
int col[N];
stack<int > st;
bool vis[N];
void tarjan(int u)
{
    dfn[u]=low[u]=++dep;
    vis[u]=true;
    st.push(u);
    
    for(int i=h[u];i;i=ne[i])
    {
        int v=e[i];
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v])low[u]=min(low[u],dfn[v]);
    }
    
    if(low[u]==dfn[u])
    {
        int y;
        cnt++;
        do
        {
            y=st.top();
            st.pop();
            vis[y]=false;
            col[y]=cnt;
        }while(y!=u);
    }
}
int ans[N];
void prepare()
{
    memset(h,0,sizeof h);
    memset(col,0,sizeof col);
    memset(dfn,0,sizeof dfn);
    memset(low,0,sizeof low);
    memset(vis,0,sizeof vis);
    idx=1;
    dep=cnt=0;
    while(!st.empty())st.pop();
}
int main()
{
    while(~scanf("%d",&n))
    {
        prepare();
        for(int i=1;i<=n;i++)
        {
            int sum;
            scanf("%d",&sum);
            while(sum--)
            {
                int x;
                scanf("%d",&x);
                add(i,x+n);
            }
        }
        for(int i=1;i<=n;i++)
        {
            int x;
            scanf("%d",&x);
            add(x+n,i);
        } 
        for(int i=1;i<=2*n;i++)
            if(!dfn[i]) tarjan(i);
            
        for(int i=1;i<=n;i++)
        {
            int sum=0;
            for(int j=h[i];j;j=ne[j])
            {
                int v=e[j];
                if(col[i]==col[v])
                {
                    ans[++sum]=v-n;
                }
            }
            printf("%d ",sum);
            sort(ans+1,ans+sum+1);
            for(int i=1;i<=sum;i++)printf("%d ",ans[i]);
            puts("");
        }
    }
    
    return 0;
}

                                      完结撒花