失恋阵线同盟 - jiyanfeng1的专栏 - 博客频道 - CSDN.NET

失恋阵线同盟 - jiyanfeng1的专栏 - 博客频道 - CSDN.NET

[description] 莉莉安女学园的少女们，今天也带着无垢的笑容，穿过等身高的校门。但是，鲜为人知的是，每个少女都暗恋着另一位同学。而害羞的少女们都没有对对方表白。也许是怕说出以后，得到的回答不是自己希望听到的吧。毕竟，大多数人是单恋，而像A喜欢B，B喜欢C，C喜欢D，。。。，F喜欢G,G又喜欢A这种情况也是很常见的。假设没有人自恋。一些少女自发组成了"失恋阵线同盟"，目的为了互相鼓励，得到意中人的认可。组成同盟唯一的条件是，"同盟"中的任意两个人不能有"喜欢"的关系，也就是"互不喜欢"。现在，告诉你每一位少女恋慕的对象，请计算一下，"失恋阵线同盟"的人数，最大有多大？ 
  
[input] 输入分两行。第一行是一个自然数N。（2<=N<=1000000）  第二行包含N个自然数a[1],a[2],...,a[N]，以空格隔开。（1<=a[i]<=N，a[i]!=i） a[i]=j表示：少女i喜欢少女j。 
  
[output] 输出一个自然数s，s是"同盟"的最大大小。 即：求最大的s，使得：存在相异整数b[1],b[2],...,b[s]（都在1..N的范围内），使得：{a[b[1]],a[b[2]],...,a[b[s]]}与{b[1],b[2],...,b[s]}没有交集。 
  
[sample input] 
6 
2 3 4 2 6 5 
  
[sample output] 
3 
  
[hint] 第一位少女没人喜欢，她可以加入；因为2,3,4是一个圈圈，所以她们中间只能选1个人；5,6互相喜欢，所以只能选一个人。一种可能的选法是选{1,3,5}四人组成同盟。 
  
[hint2] 如果存在K使得N>=3K，那么至少可以选出K个人组成同盟。可以证明。 

思路:

本问题等价于求解最大独立集。构建一个图，图的每个节点代表一个学生，如果两个学生之间有喜欢或者被喜欢的关系，那么他们之间连一条边。求最大失恋同盟，等价于求解最大独立集。注意，此题假设女同学们都是同性恋。

Read full article from 失恋阵线同盟 - jiyanfeng1的专栏 - 博客频道 - CSDN.NET