編程算法 - 食物鏈 並查集 代碼(C)

編程算法 - 食物鏈 並查集 代碼(C)

食物鏈 並查集 代碼(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