因为是完美匹配，所以每个点都已经匹配了，那么如果要选择一条别的边，增光路的最后必定找到原来所匹配的点，加上匹配的边，那么就是一个环。所以可选边在一个强连通分量里。
#include#include #include using namespace std;const int maxn=4e3+9;int mt[maxn];int low[maxn],dfn[maxn],instack[maxn],count;int s[maxn],stack[maxn],top,con;int head[maxn],lon;int ans[maxn],n;struct{ int next,to;}e[200000+maxn];void edgeini(){ memset(head,-1,sizeof(head)); lon=-1;}void edgemake(int from,int to){ e[++lon].to=to; e[lon].next=head[from]; head[from]=lon;}void tarjan(int t){ low[t]=dfn[t]=++count; instack[t]=1; stack[++top]=t; for(int k=head[t],u;k!=-1;k=e[k].next) { u=e[k].to; if(dfn[u]==-1) { tarjan(u); low[t]=min(low[t],low[u]); } else if(instack[u]) { low[t]=min(low[t],dfn[u]); } } if(low[t]==dfn[t]) { ++con; while(1) { int u=stack[top--]; s[u]=con; instack[u]=0; if(u==t) break; } }}void tarjan(){ memset(dfn,-1,sizeof(dfn)); memset(instack,0,sizeof(instack)); top=count=con=0; for(int i=1;i<=n;i++) if(dfn[i]==-1) { tarjan(i); }}int main(){// freopen("in.txt","r",stdin); while(scanf("%d",&n)!=EOF) { edgeini(); for(int i=1,tmp;i<=n;i++) { scanf("%d",&tmp); for(int j=1,to;j<=tmp;j++) { scanf("%d",&to); edgemake(i,to+n); } } for(int i=1;i<=n;i++) { scanf("%d",&mt[i]); edgemake(mt[i]+n,i); } tarjan(); for(int i=1;i<=n;i++) { memset(ans,0,sizeof(ans)); int sum=0; for(int k=head[i];k!=-1;k=e[k].next) { int u=e[k].to; if(s[i]==s[u]) { sum++; ans[u-n]=1; } } printf("%d",sum); for(int i=1;i<=n;i++) if(ans[i]) printf(" %d",i); printf("\n"); } } return 0;}