kuangbin 專題五：並查集 The Suspects

題目連結：
傳送門

1.做法一

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 30010;
int parent[N], r[N], n, m, ans;

//初始化
void init() {
	memset(parent, -1, sizeof(parent));
	memset(r, 0, sizeof(r));
}

//找到根結點
int findRoot(int x) {
	int xRoot = x;
	while(parent[xRoot] != -1)
		xRoot = parent[xRoot];
	return xRoot;
}

//判斷是否同組
bool sameGroup(int x, int y) {
	int xRoot = findRoot(x);
	int yRoot = findRoot(y);
	return xRoot == yRoot;
}

//連線兩個結點
void merge(int x, int y) {
	int xRoot = findRoot(x);
	int yRoot = findRoot(y);
	if(xRoot != yRoot) {
		if(r[xRoot] > r[yRoot]) {
			parent[yRoot] = xRoot;
		} else if(r[xRoot] < r[yRoot]) {
			parent[xRoot] = yRoot;
		} else {
			parent[xRoot] = yRoot;
			r[yRoot]++;
		}
	}
}

int main() {
	while(scanf("%d%d", &n, &m) != EOF) {
		if(n == 0 && m == 0) break;
        //初始化
		init();
        //輸入每一組
		for(int i = 0; i < m; i++) {
			int tmp, cur, t;
            //先讀入該組的大小和第一個點
			scanf("%d%d", &t, &cur);
            //把第一個點和其他結點連在一起
			for(int j = 1; j < t; j++) {
				scanf("%d", &tmp);
				merge(cur, tmp);
			}
		}
        //找到0點的根結點
		int std = findRoot(0);
		ans = 0; 
        //遍歷看看有多少個和其同根的結點（包括根節點本身）
		for(int i = 0; i < n; i++)
		{
			int curnum = findRoot(i);
			if(curnum == std) ans++;
		}
        //輸出結果
		printf("%d\n", ans);
	}
	return 0;
}

第一種做法就是先記錄人數和組數，然後再把每組的第一個人與其他人連線起來，這些都是並查集的基本操作。然後重點在於最後的判斷，第一種做法的判斷方法是，把0點的根結點找出來，然後遍歷所有點，看看有多少點和0點的根結點是相同的。統計完以後輸出答案。

2.做法二

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 30010;
//amount陣列用於儲存當前結點的子元素+自己的數量
int parent[N], r[N], amount[N], n, m;

//初始化資料
void init() {
	memset(parent, -1, sizeof(parent));
	memset(r, 0, sizeof(r));
    //先加上自己
	for(int i = 0; i < n; i++)
		amount[i] = 1;
}

//找到根結點
int findRoot(int x) {
	int xRoot = x;
	while(parent[xRoot] != -1)
		xRoot = parent[xRoot];
	return xRoot;
}

//判斷是否同組（這裡沒用到，我也忘了刪）
bool sameGroup(int x, int y) {
	int xRoot = findRoot(x);
	int yRoot = findRoot(y);
	return xRoot == yRoot;
}

//連線兩個結點，同時維護一個陣列用於儲存當前組的元素數量
void merge(int x, int y) {
	int xRoot = findRoot(x);
	int yRoot = findRoot(y);
	if(xRoot != yRoot) {
		if(r[xRoot] > r[yRoot]) {
			parent[yRoot] = xRoot;
			amount[xRoot] += amount[yRoot];
		} else if(r[xRoot] < r[yRoot]) {
			parent[xRoot] = yRoot;
			amount[yRoot] += amount[xRoot];
		} else {
			parent[xRoot] = yRoot;
			r[yRoot]++;
			amount[yRoot] += amount[xRoot];
		}
	}
}

int main() {
	while(scanf("%d%d", &n, &m) != EOF) {
        //跳出條件
		if(n == 0 && m == 0) break;
        //初始化
		init();
        //輸入各組
		for(int i = 0; i < m; i++) {
			int tmp, cur, t;
            //記錄下每一組人數，同時記下第一個人
			scanf("%d%d", &t, &cur);
            //那第一個人和其他人連線
			for(int j = 1; j < t; j++) {
				scanf("%d", &tmp);
				merge(cur, tmp);
			}
		}
        //找到0號的根結點
		int std = findRoot(0);
        //輸出0的根結點的子元素+自己的數量
		printf("%d\n", amount[std]);
	}
	return 0;
}

這種做法的基本思路與前一種差不多，根本區別在於記錄人數的方法。在這種方法中，建立了一個amount陣列用於儲存其子元素的數量，每次連線時都會處理amount陣列，來存下當前點的子結點的數量。因為最終我們要的是其子結點和它本身，所以amount初始化為1。最後找出0的根結點，然後輸出amount[std]（std為0的根結點）就好了。