参考资料：
[1]:
[2]:
[3]:
题意：
有n个王子，每个王子都有k个喜欢的妹子，每个王子只能和喜欢的妹子结婚，大臣给出一个匹配表，每个王子都和一个妹子结婚，但是国王不满意，他要求大臣给他另一个表，每个王子可以和几个妹子结婚，按序号升序输出妹子的编号，这个表应满足所有的王子最终都有妹子和他结婚。
分析：
很好的图论题，把强连通分量和完美匹配结合起来了。
2*N 个顶点的2 分图，并且给了一个完美匹配(Perfect Matching)以及每个顶点可以连接的其他的顶点。
题目要求是否可以确定某 2 个顶点连边后，其他 2*(N - 1) 个顶点的 2 分图是否可以构成完美匹配。
建图：
如果王子u喜欢妹子v，则建一条边u指向v(u,v)，对于大臣给出的初始完美匹配，如果王子u和妹子v结婚，则建一条边v指向u(v,u)，然后求强连通分量。
对于每个王子和妹子，如果他们都在同一个强连通分量内，则他们可以结婚。
为什么呢？因为每个王子只能和喜欢的妹子结婚，初始完美匹配中的丈夫和妻子之间有两条方向不同的边可以互达，则同一个强连通分量中的王子数和妹子数一定是相等的，若王子 x 可以和另外的一个妹子 a 结婚，妹子 a 的原配王子 y 肯定能找到另外一个妹子 b 结婚，因为如果找不到的话，则 x 和 a 必不在同一个强连通分量中。
所以一个王子可以和所有与他同一强连通分量的妹子结婚，而这不会导致同一强连通分量中的其他王子找不到妹子结婚。
（证明：王子为什么不能选择不同强连通分量的妹子：
反证法：如果强连通分量 1 中的王子选择了强连通分量 2 中的妹子,那么势必强连通分量 2 中的一个王子无法在自己的强连通分量中找到妹子,那么他就会去别的强连通分量找妹子,这样一直循环下去，我们知道最终一定是经过了强连通分量 1,2,x1,x2,xn,……,1，王子们才能都找到自己的妹子，这样这些强连通分量1,2,x1,x2,xn,……,1会构成一个强连通分量,与题设在不同强连通分量中找妹子不符）
此题难点：建图
AC代码：
这一题的数据量挺大的，光是输入输出就会消耗很多时间了，可以用输入输出外挂来加速读入和输出。
Kosaraju算法：
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 #define mem(a,b) memset(a,b,sizeof a) 8 #define pb push_back 9 const int maxV=4e3+50;10 11 int scc[maxV];12 bool vis[maxV];13 vector vs;14 vector edge[maxV],redge[maxV];15 16 void addEdge(int u,int v)17 {18 edge[u].pb(v);19 redge[v].pb(u);20 }21 void Dfs(int u)22 {23 vis[u]=true;24 for(int i=0;i < edge[u].size();++i)25 {26 int to=edge[u][i];27 if(!vis[to])28 Dfs(to);29 }30 vs.pb(u);31 }32 void rDfs(int u,int sccId)33 {34 scc[u]=sccId;35 vis[u]=true;36 for(int i=0;i < redge[u].size();++i)37 {38 int to=redge[u][i];39 if(!vis[to])40 rDfs(to,sccId);41 }42 }43 void Scc(int maxV)44 {45 mem(vis,false);46 vs.clear();47 for(int i=1;i <= maxV;++i)48 if(!vis[i])49 Dfs(i);50 mem(vis,false);51 int sccId=0;52 for(int i=vs.size()-1;i >= 0;--i)53 {54 int v=vs[i];55 if(!vis[v])56 {57 sccId++;58 rDfs(v,sccId);59 }60 }61 }62 int main()63 {64 int N;65 scanf("%d",&N);66 for(int i=1;i <= N;++i)67 {68 int k,v;69 scanf("%d",&k);70 while(k--)71 {72 scanf("%d",&v);73 addEdge(i,v+N);//王子i喜欢妹子v74 }75 }76 for(int i=1;i <= N;++i)77 {78 int v;79 scanf("%d",&v);80 addEdge(v+N,i);//王子i可以和妹子v结婚81 }82 Scc(N);83 for(int i=1;i <= N;++i)84 {85 int res=0;86 int ans[maxV];87 for(int j=0;j < edge[i].size();++j)88 {89 int to=edge[i][j];90 if(scc[i] == scc[to])//同一个强连通分量91 ans[res++]=to;92 }93 sort(ans,ans+res);94 printf("%d",res);95 for(int j=0;j < res;++j)96 printf(" %d",ans[j]-N);97 printf("\n");98 }99 }
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 #define mem(a,b) memset(a,b,sizeof a) 8 #define pb push_back 9 const int maxV=4e3+50; 10 11 int scc[maxV]; 12 bool vis[maxV]; 13 vector vs; 14 vector edge[maxV],redge[maxV]; 15 16 void addEdge(int u,int v) 17 { 18 edge[u].pb(v); 19 redge[v].pb(u); 20 } 21 void Dfs(int u) 22 { 23 vis[u]=true; 24 for(int i=0;i < edge[u].size();++i) 25 { 26 int to=edge[u][i]; 27 if(!vis[to]) 28 Dfs(to); 29 } 30 vs.pb(u); 31 } 32 void rDfs(int u,int sccId) 33 { 34 scc[u]=sccId; 35 vis[u]=true; 36 for(int i=0;i < redge[u].size();++i) 37 { 38 int to=redge[u][i]; 39 if(!vis[to]) 40 rDfs(to,sccId); 41 } 42 } 43 void Scc(int maxV) 44 { 45 mem(vis,false); 46 vs.clear(); 47 for(int i=1;i <= maxV;++i) 48 if(!vis[i]) 49 Dfs(i); 50 mem(vis,false); 51 int sccId=0; 52 for(int i=vs.size()-1;i >= 0;--i) 53 { 54 int v=vs[i]; 55 if(!vis[v]) 56 { 57 sccId++; 58 rDfs(v,sccId); 59 } 60 } 61 } 62 //===============输入输出挂=============== 63 int Scan() //输入外挂 64 { 65 int res=0,ch,flag=0; 66 if((ch=getchar())=='-') 67 flag=1; 68 else if(ch>='0'&&ch<='9') 69 res=ch-'0'; 70 while((ch=getchar())>='0'&&ch<='9') 71 res=res*10+ch-'0'; 72 73 return flag?-res:res; 74 } 75 void Out(int a) //输出外挂 76 { 77 if(a>9) 78 Out(a/10); 79 putchar(a%10+'0'); 80 } 81 //======================================== 82 int main() 83 { 84 int N; 85 scanf("%d",&N); 86 for(int i=1;i <= N;++i) 87 { 88 int k,v; 89 //scanf("%d",&k); 90 k=Scan(); 91 while(k--) 92 { 93 //scanf("%d",&v); 94 v=Scan(); 95 addEdge(i,v+N);//王子i喜欢妹子v 96 } 97 } 98 for(int i=1;i <= N;++i) 99 {100 int v;101 //scanf("%d",&v);102 v=Scan();103 addEdge(v+N,i);//王子i可以和妹子v结婚104 }105 Scc(N);106 for(int i=1;i <= N;++i)107 {108 int res=0;109 int ans[maxV];110 for(int j=0;j < edge[i].size();++j)111 {112 int to=edge[i][j];113 if(scc[i] == scc[to])//同一个强连通分量114 ans[res++]=to;115 }116 sort(ans,ans+res);117 //printf("%d",res);118 Out(res);119 for(int j=0;j < res;++j)120 {121 printf(" ");122 Out(ans[j]-N);123 //printf(" %d",ans[j]-N);124 }125 printf("\n");126 }127 }
好晚了，身心疲惫，明天在补Tarjan算法...............