题意：

　　给出集合U,V，集合U有n个元素，集合V有m个元素；

　　有 m 个操作，m_i : s₁ s₂ 有一条s₁指向s₂的边（s₁,s₂可能属于第三个集合，暂且称之为K集合）；

　　指向边具有传递性，即 A->B,B->C <=> A->C

　　求V集合中被 U 指向的元素；

题解：

　　并查集debug个了两天，始终wa，今天上午上数字逻辑课的时候，灵光一闪，又想到了一个可能会出错的点；

　　经过一番挣扎，终于判断了此题不能用并查集做，蓝瘦香菇~~~~~~

　　还记得并查集中的Union(x,y)操作吗？

　　此函数得作用是将 x元素 所在的集合与 y元素 所在得集合合并成一个大集合；

　　对于此题，初始想法是，并查集中只保存

　　　　①U 集合指出去的边

　　　　②K 集合指向 V 集合的边

　　　　③V 集合指向 V 集合的边

　　如果满足上述三种条件，则Union(s₁,s₂)；

　　最后，判断V集合中元素的Find(s)是否属于U集合，如果属于，则输出s；

　　那么，问题来了，s₁,s₂真的可以这么合并吗？

　　看如下连接方式：

　　

　　输入的顺序是：

　　　　v₂ v₁

　　　　k₂ v₁

　　对于第一条指令，Union(v₂,v₁)是没得说的，此时 fa(v₁) = v₂ , fa(v₂) =v₂；

　　对于第二条指令，可以调用 Union(k₂,v₁) 吗？

　　先看看调用后的结果：Find(k₂) = k₂ , Find(v₁) = v₂ , k₂ ≠ v₂ , fa(v₁)=fa(v₂)=k_2； ???

　　那么，再加入一条边呢？

　　　　u₁ k₂

　　

　　那么，此时调用Union(u₁,k₂) : fa(k₂) = u₁;

　　当输出时：

　　　　v₁ : Find(v₁) = Find(k₂) = u₁ ，输出 v₁

　　　　v₂ : Find(v₂) = Find(k₂) = u₁ ，输出 v₂ 

　　这就出现问题了吧！！！

　　那，如果人为的将 fa(v₁) = k₂，但是fa(v₂) = v₂呢？

　　看一下接下来的这张图：

　　加入边 u₂ v₂

　　

　　

　　输出时：

　　　　v₁ : Find(v₁) = k₂ ，不输出 v₁

　　　　v₂ : Find(v₂) = u₂ ，输出 v₂

　　又出现错误了，是吧！ 

 

　　为什么并查集会出现这个问题呢？

　　v₁,v₂属于同一个集合，v₁,k₂属于同一个集合，但 k₂,v₂并不能属于同一个集合，所以不能合并；

　　看来，当图是有向图时，慎用并查集!!!!!!!!!!!!!

　　

　　所以说，还是搜索大法好！！！！

AC代码：

1 #include
      
         2 #include
       
          3 #include