题目链接：

题意：有n个王子，每个王子都有k个喜欢的妹子，每个王子只能和喜欢的妹子结婚，大臣给出一个匹配表，每个王子都和一个妹子结婚，但是国王不满意，他要求大臣给他另一个表，每个王子可以和几个妹子结婚，按序号升序输出妹子的编号，这个表应满足所有的王子最终都有妹子和他结婚。

分析：很好的图论题，把强连通分量和完美匹配结合起来了，记得多校的时候看到类似的题目（），但是不会做，还以为是二分匹配=_=

首先建图，如果王子u喜欢妹子v，则建一条边u指向v(u,v)，对于大臣给出的初始完美匹配，如果王子u和妹子v结婚，则建一条边v指向u(v,u)，然后求强连通分量，

对于每个王子和妹子，如果他们都在同一个强连通分量内，则他们可以结婚。

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

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

好像很绕的样子@_@。。。。。大家在纸上画画图吧

建图的时候王子从1~n编号，妹子从n+1~2*n编号

这一题的数据量挺大的，光是输入输出就会消耗很多时间了，可以用输入输出外挂来加速读入和输出。

不加输入外挂9000+ms

加输入外挂8000+ms

加输入输出外挂500+ms

AC代码：

1 #include
      
         2 #include
       
          3 #include
        
           4 using namespace std;  5   6 const int N=4000+5;  7 const int M=200000+4000;  8 struct EDGE{  9     int v,next; 10 }edge[M]; 11 int first[N],low[N],dfn[N],sta[M],belong[N],ans[N]; 12 bool instack[N]; 13 int g,cnt,top,scc; 14  15 void AddEdge(int u,int v) 16 { 17     edge[g].v=v; 18     edge[g].next=first[u]; 19     first[u]=g++; 20 } 21 int min(int a,int b) 22 { 23     return a
         
          ='0'&&ch<='9') 61         res=ch-'0'; 62     while((ch=getchar())>='0'&&ch<='9') 63         res=res*10+ch-'0'; 64     return flag?-res:res; 65 } 66 void Out(int a)    //输出外挂 67 { 68     if(a>9) 69         Out(a/10); 70     putchar(a%10+'0'); 71 } 72 int main() 73 { 74     int n,i,u,v,k; 75     while(scanf("%d",&n)!=EOF) 76     { 77         g=cnt=top=scc=0; 78         memset(first,-1,sizeof(first)); 79         memset(dfn,0,sizeof(dfn)); 80         memset(instack,false,sizeof(instack)); 81         for(i=1;i<=n;i++) 82         { 83         //    scanf("%d",&k); 84             k=Scan(); 85             while(k--) 86             { 87             //    scanf("%d",&v); 88                 v=Scan(); 89                 AddEdge(i,v+n);      //王子i喜欢妹子v 90             } 91         } 92         for(i=1;i<=n;i++) 93         { 94         //    scanf("%d",&v); 95             v=Scan(); 96             AddEdge(v+n,i);       //王子i可以和妹子v结婚 97         } 98  99         for(i=1;i<=2*n;i++)    //求强连通分量100             if(!dfn[i])101                 Tarjan(i);102 103         for(u=1;u<=n;u++)104         {105             int count=0;106             for(i=first[u];i!=-1;i=edge[i].next)107             {108                 v=edge[i].v;109                 if(belong[u]==belong[v])   //同一个强连通分量110                     ans[count++]=v-n;111             }112             sort(ans,ans+count);113         //    printf("%d",count);114             Out(count);115             for(i=0;i