Problem

求出能打开所有存钱罐的情况下，需要破坏的存钱罐的最少数量

Solution

这道题让你求出连通块的个数。而将一个存钱罐钥匙放在另一个存钱罐十分像并查集中的合并。所以这道题可以用并查集做。

1：初始化并查集

void Init () {
	for (int i = 1; i < _maxNum + 1; i++) {
		_father[i] = i;//每个人的初始父亲都是他自己
	}
}

2：查找

int Find (int x) {
	while (_father[x] != x) {
		x = _father[x] = Find(_father[x]);//递归，路径压缩
	}
	
	return x;
}

3：合并

void Merge (int one, int two) {
    _father[Find(one)] = Find(two);//将两个节点合并到一起
}

4：查找连通块

for (int i = 1; i < _maxNum + 1; i++) {
	if (_father[i] == i) {
		_ans++;//如果找到了结果加一
	}
}

然后，我们就可以愉快的AC了

ACCode

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>

using namespace std;

int _maxNum;
int _father[1000009];
int _ans = 0;

int Find (int x) {
	while (_father[x] != x) {
		x = _father[x] = Find(_father[x]);
	}
	
	return x;
}

void Init () {
	for (int i = 1; i < _maxNum + 1; i++) {
		_father[i] = i;
	}
}

void Merge (int one, int two) {
    _father[Find(one)] = Find(two);
}

void ParseIn () {
	int curInt;
	scanf("%d", &_maxNum);
	Init();
	
	for (int i = 1; i < _maxNum + 1; i++) {
		scanf("%d", &curInt);
		Merge(curInt, i);
	}
}

void Core () {
	for (int i = 1; i < _maxNum + 1; i++) {
		if (_father[i] == i) {
			_ans++;
		}
	}
}

void CWriteOut () {
	printf("%d\n", _ans);
}

int main () {

	ParseIn();
	Core();
	CWriteOut();

	return 0;
}