UESTC 898 方老师和缘分 --二分图匹配+强连通分量

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

这题原来以为是某种匹配问题，后来好像说是强连通的问题。

做法：建图，每个方老师和它想要的缘分之间连一条有向边，然后，在给出的初始匹配中反向建边，即如果第i个方老师现在找到的是缘分u，则建边u->i。这样求出所有的强连通分量，每个强连通分量中方老师和缘分的数目一定是相等的，所以每个方老师一定可以找到与他在同一个强连通分量里的缘分，因为强连通分量中每个点都是可达的，某个方老师找到了其强连通分量中的非原配点，则该原配缘分一定可以在强连通分量中找到"新欢"。可以画个图看看。

由于要构造非二分图，缘分的编号从n+1开始，到2n。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#define Mod 1000000007
using namespace std;
#define N 200007std::vector<int> G[];
int low[],dfn[];
int instk[],bel[];
int n,Time,cnt,res;
stack<int> stk;
int ans[];void Tarjan(int u)
{
low[u] = dfn[u] = ++Time;
stk.push(u);
instk[u] = ;
for(int i=;i<G[u].size();i++)
{
int v = G[u][i];
if(!dfn[v])
{
Tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(instk[v])
low[u] = min(low[u],dfn[v]);
}
if(low[u] == dfn[u])
{
cnt++;
int v;
do
{
v = stk.top();
stk.pop();
instk[v] = ;
bel[v] = cnt;
}while(u != v);
}
}void init()
{
memset(G,,sizeof(G));
memset(instk,,sizeof(instk));
memset(bel,-,sizeof(bel));
memset(low,,sizeof(low));
memset(dfn,,sizeof(dfn));
Time = cnt = ;
while(!stk.empty())
stk.pop();
}int main()
{
int i,j,u,v,k;
while(scanf("%d",&n)!=EOF)
{
init();
for(i=;i<=n;i++)
{
scanf("%d",&k);
while(k--)
{
scanf("%d",&v);
G[i].push_back(v+n);
}
}
for(i=;i<=n;i++)
{
scanf("%d",&v);
G[v+n].push_back(i);
}
for(i=;i<=n;i++)
{
if(!dfn[i])
Tarjan(i);
}
for(u=;u<=n;u++)
{
k = ;
for(i=;i<G[u].size();i++)
{
v = G[u][i];
if(bel[u] == bel[v])
ans[k++] = v-n;
}
sort(ans,ans+k);
printf("%d",k);
for(i=;i<k;i++)
printf(" %d",ans[i]);
printf("\n");
}
}
return ;
}