小韋老師@神犇營-my0411-團夥

題目：

描述

在某城市裡住着 n 個人，任何兩個認識的人不是朋友就是敵人，而且滿足：

1、我朋友的朋友是我的朋友；

2、我敵人的敵人是我的朋友；

所有是朋友的人組成一個團夥。告訴你關于這 n 個人的 m 條資訊，即某兩個人是朋友，或者某兩個人是敵人，請你編寫一個程式，計算出這個城市最多可能有多少個團夥？

輸入

第 1 行為 n 和 m，1 < n < 1000 , 1 <= m <= 100 000；以下 m 行，每行為 p x y，p 的值為 0 或 1，p 為 0 時，表示 x 和 y 是朋友，p 為 1 時，表示 x 和 y 是敵人。

輸出

一個整數，表示這 n 個人最多可能有幾個團夥。

輸入樣例1

6 4
1 1 4
0 3 5
0 4 6
1 1 2
           

輸出樣例1

3
           

題解：

思路

整體思路：

用 a 表示 a 的朋友；

a + n 表示 a 的敵人。

如果 a 和 b 是朋友，合并 a 所在集合和 b 所在集合；

如果 a 和 b 是敵人，合并 a + n 所在集合和 b 所在集合，b + n 所在集合和 a 所在集合。

具體步驟：

1. 定義兩個數組：

// 數組要開成人數的兩倍加 10，因為要把 i + n 當作 i 的敵人 
    const int N = 2e3 + 10;  
    int father[N];  // 父親數組 
    bool isRoot[N];  // 根數組，一開始都初始化為 false 
           

1. 調用初始化函數進行初始化：

init(n);
           

1. 輸入 m 組資料：

for (int i = 0; i < m; i++) {
    	cin >> p >> x >> y;
    	if (p == 0) {  // 若 x 和 y 是朋友，則合并 x 和 y 
    		Union(x, y);
    	} else {  // 若 x 和 y 是敵人 
    		Union(x + n, y);  // 合并 x 的敵人 
    		Union(x, y + n);  // 合并 y 的敵人 
    	}
    } 
           

1. 數有多少個根，即有多少個集合（有多少個團夥）：

int cnt = 0;  // 計數器 
	for (int i = 1; i <= n; i++) {  // 枚舉 1~n 
		int t = findFather(i);  // 找到 i 的根 
		if (!isRoot[t]) {  // 若該根未被标記（每個根隻能數一次） 
			isRoot[t] = true;  // 置為 true，說明已标記 
			cnt++;  // 計數器加 1 
		}
	}
           

1. 初始化函數 init 的實作：

// 初始化數組，1~n 是自己，n+1 ~ n+n 是 1~n 的敵人 
	void init(int n) {
		for (int i = 1; i <= 2*n; i++) {
			father[i] = i;
		}
	}
           

1. 合并函數的實作：

// 合并 x 所在集合和 y 所在集合 
	void Union(int x, int y) {
		int faX = findFather(x);
		int faY = findFather(y);
		if (faX != faY) {
			father[faY] = faX;
		}
	}
           

1. 查找集合的根的函數的實作：

// 查找 x 所在的集合的根 
	int findFather(int x) {
		int a = x;
		while (x != father[x]) {
			x = father[x];
		} 
		// 壓縮路徑（在時間要求不太嚴格時可以不寫） 
		while (a != father[a]) {
			int z = a;
			a = father[a];
			father[z] = x;
		}
		return x;  // 傳回根 
	}
           

思考：

1° 為什麼第 4 步要那樣去數集合的根，換個方式行嗎？例如數有多少個 father[i] == i ？

2° 該題解中對于“敵人的敵人是朋友”的處理方式給你什麼樣的啟發？

完整代碼：

#include <bits/stdc++.h>

using namespace std;

// 數組要開成人數的兩倍加 10，因為要把 i + n 當作 i 的敵人 
const int N = 2e3 + 10;  
int father[N];  // 父親數組 
bool isRoot[N];  // 根數組，一開始都初始化為 false 
int n, m;

// 初始化數組，1~n 是自己，n+1 ~ n+n 是 1~n 的敵人 
void init(int n) {
	for (int i = 1; i <= 2*n; i++) {
		father[i] = i;
	}
}

// 查找 x 所在的集合的根 
int findFather(int x) {
	int a = x;
	while (x != father[x]) {
		x = father[x];
	} 
	// 壓縮路徑（在時間要求不太嚴格時可以不寫） 
	while (a != father[a]) {
		int z = a;
		a = father[a];
		father[z] = x;
	}
	return x;  // 傳回根 
}

// 合并 x 所在集合和 y 所在集合 
void Union(int x, int y) {
	int faX = findFather(x);
	int faY = findFather(y);
	if (faX != faY) {
		father[faY] = faX;
	}
} 
 
int main() {
	
	cin >> n >> m;
	init(n);  // 記得要調用初始化函數 
	int p, x, y;
	for (int i = 0; i < m; i++) {
		cin >> p >> x >> y;
		if (p == 0) {  // 若 x 和 y 是朋友，則合并 x 和 y 
			Union(x, y);
		} else {  // 若 x 和 y 是敵人 
			Union(x + n, y);  // 合并 x 的敵人 
			Union(x, y + n);  // 合并 y 的敵人 
		}
	}
	int cnt = 0;  // 計數器 
	for (int i = 1; i <= n; i++) {  // 枚舉 1~n 
		int t = findFather(i);  // 找到 i 的根 
		if (!isRoot[t]) {  // 若該根未被标記（每個根隻能數一次） 
			isRoot[t] = true;  // 置為 true，說明已标記 
			cnt++;  // 計數器加 1 
		}
	}
	cout << cnt;  // 輸出結果 

	return 0;
}
           

我是小韋老師，企者不立，跨者不行，每天進步一點點。

歡迎大家多多交流，如果發現有錯誤，請多指正。有疑問的同學也可以留言評論或者發郵件。郵箱：[email protected]