https://www.cnblogs.com/violet-acmer/p/9739990.html
参考资料：
[1]:http://www.cnblogs.com/frog112111/p/3384261.html
[2]:https://blog.csdn.net/a709743744/article/details/52133778
[3]:http://www.cppblog.com/Uriel/articles/121169.html
题意：
有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算法：
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
#define mem(a,b) memset(a,b,sizeof a)
#define pb push_back
const int maxV=4e3+; int scc[maxV];
bool vis[maxV];
vector<int >vs;
vector<int >edge[maxV],redge[maxV]; void addEdge(int u,int v)
{
edge[u].pb(v);
redge[v].pb(u);
}
void Dfs(int u)
{
vis[u]=true;
for(int i=;i < edge[u].size();++i)
{
int to=edge[u][i];
if(!vis[to])
Dfs(to);
}
vs.pb(u);
}
void rDfs(int u,int sccId)
{
scc[u]=sccId;
vis[u]=true;
for(int i=;i < redge[u].size();++i)
{
int to=redge[u][i];
if(!vis[to])
rDfs(to,sccId);
}
}
void Scc(int maxV)
{
mem(vis,false);
vs.clear();
for(int i=;i <= maxV;++i)
if(!vis[i])
Dfs(i);
mem(vis,false);
int sccId=;
for(int i=vs.size()-;i >= ;--i)
{
int v=vs[i];
if(!vis[v])
{
sccId++;
rDfs(v,sccId);
}
}
}
int main()
{
int N;
scanf("%d",&N);
for(int i=;i <= N;++i)
{
int k,v;
scanf("%d",&k);
while(k--)
{
scanf("%d",&v);
addEdge(i,v+N);//王子i喜欢妹子v
}
}
for(int i=;i <= N;++i)
{
int v;
scanf("%d",&v);
addEdge(v+N,i);//王子i可以和妹子v结婚
}
Scc(N);
for(int i=;i <= N;++i)
{
int res=;
int ans[maxV];
for(int j=;j < edge[i].size();++j)
{
int to=edge[i][j];
if(scc[i] == scc[to])//同一个强连通分量
ans[res++]=to;
}
sort(ans,ans+res);
printf("%d",res);
for(int j=;j < res;++j)
printf(" %d",ans[j]-N);
printf("\n");
}
}
不用输入输出挂
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
#define mem(a,b) memset(a,b,sizeof a)
#define pb push_back
const int maxV=4e3+; int scc[maxV];
bool vis[maxV];
vector<int >vs;
vector<int >edge[maxV],redge[maxV]; void addEdge(int u,int v)
{
edge[u].pb(v);
redge[v].pb(u);
}
void Dfs(int u)
{
vis[u]=true;
for(int i=;i < edge[u].size();++i)
{
int to=edge[u][i];
if(!vis[to])
Dfs(to);
}
vs.pb(u);
}
void rDfs(int u,int sccId)
{
scc[u]=sccId;
vis[u]=true;
for(int i=;i < redge[u].size();++i)
{
int to=redge[u][i];
if(!vis[to])
rDfs(to,sccId);
}
}
void Scc(int maxV)
{
mem(vis,false);
vs.clear();
for(int i=;i <= maxV;++i)
if(!vis[i])
Dfs(i);
mem(vis,false);
int sccId=;
for(int i=vs.size()-;i >= ;--i)
{
int v=vs[i];
if(!vis[v])
{
sccId++;
rDfs(v,sccId);
}
}
}
//===============输入输出挂===============
int Scan() //输入外挂
{
int res=,ch,flag=;
if((ch=getchar())=='-')
flag=;
else if(ch>=''&&ch<='')
res=ch-'';
while((ch=getchar())>=''&&ch<='')
res=res*+ch-''; return flag?-res:res;
}
void Out(int a) //输出外挂
{
if(a>)
Out(a/);
putchar(a%+'');
}
//========================================
int main()
{
int N;
scanf("%d",&N);
for(int i=;i <= N;++i)
{
int k,v;
//scanf("%d",&k);
k=Scan();
while(k--)
{
//scanf("%d",&v);
v=Scan();
addEdge(i,v+N);//王子i喜欢妹子v
}
}
for(int i=;i <= N;++i)
{
int v;
//scanf("%d",&v);
v=Scan();
addEdge(v+N,i);//王子i可以和妹子v结婚
}
Scc(N);
for(int i=;i <= N;++i)
{
int res=;
int ans[maxV];
for(int j=;j < edge[i].size();++j)
{
int to=edge[i][j];
if(scc[i] == scc[to])//同一个强连通分量
ans[res++]=to;
}
sort(ans,ans+res);
//printf("%d",res);
Out(res);
for(int j=;j < res;++j)
{
printf(" ");
Out(ans[j]-N);
//printf(" %d",ans[j]-N);
}
printf("\n");
}
}
调用输入输出挂
好晚了，身心疲惫，明天在补Tarjan算法...............