食物链 并查集 代码(C)

?

?

题目: 有N只动物, 分别编号为1,2,...,N. 所有动物都属于A,B,C中的一种. 已知A吃B, B吃C, C吃A.

按顺序给出两种信息K条.

第一种: x和y属于同一类.

第二种: x吃y.

信息之间可能会出错和矛盾, 求不正确的信息数.

?

例如:

有N=10只动物, 给定K=7条信息.

(1) 1: x=101, y=1; 出错:没有101的动物.

(2) 2: x=1, y=2; 动物1吃动物2.

(3) 2: x=2, y=3; 动物2吃动物3.

(4) 2: x=3, y=3; 出错, 动物3不能吃动物3.

(5) 1: x=1, y=3; 出错, 动物1和动物3属于同一种, 与(2)(3)矛盾.

(6) 2: x=3, y=1; 动物3吃动物1.

(7) 1: x=5, y=5; 动物5和动物5属于同一种.

result = 3, 即(1)(4)(5)出错.

?

使用并查集(disjoint set)求解.

创建3*N个元素的并查集.每一组表示元素i可能属于的种类x, 共3种.

然后合并并查集. 找到矛盾信息.

?

代码:

?

/*
 * main.cpp
 *
 *  Created on: 2014.7.20
 *      Author: Spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include 
  
   

/*
 * main.cpp
 *
 *  Created on: 2014.7.20
 *      Author: spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; class DisjoinSet { static const int MAX_N = 10000; int par[MAX_N]; int rank[MAX_N]; public: void init(int n) { for (int i=0; i
        
        输出:
        
?
        
?
        
ans = 3
 
        
 
        
 
        
?
 
        
?
 
        
 
        
?
 
        
?
 
        
?