<>

题目大意：

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

解题分析：  <转载于 >

　　如果王子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会构成一个强连通分量,与题设在不同强连通分量中找妹子不符）。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6  7 #define mem(a,b) memset(a,b,sizeof(a)) 8 const int N = 5e3+10; 9 10 int n,tot,scc,top;11 int stk[N],dfn[N],low[N],belong[N],instack[N],ans[N];12 vector
         
          
            >G;13 void init(){14 tot=scc=top=0;15 mem(dfn,0);16 mem(stk,0);17 mem(low,0);18 mem(belong,0);19 mem(instack,0);20 G.clear(),G.resize(N);21 }22 void Tarjan(int u){23 low[u]=dfn[u]=++tot;24 stk[++top]=u;25 instack[u]=1;26 int v;27 for(int i=0;i
          
         
        
       
      
     

 

 

2018-11-09