刷题笔记32——STL::map实现并查集、岛问题
一、STL::map实现并查集
测试结果
代码
实现思路见 此处——并查集
#include <iostream>
#include <map>
#include <stack>
#include <vector>
using namespace std;
struct Node {
int _i; // whatever type u want
Node(int x) : _i(x) { }
Node() : _i(0) { }
friend bool operator!=(const Node &a, const Node &b) { return (a._i != b._i); }
friend bool operator==(const Node &a, const Node &b) { return (a._i == b._i); }
friend bool operator<(const Node &a, const Node &b) { return (a._i < b._i); }
};
class UnionFindSet {
public:
UnionFindSet(const vector<Node> &Nodes) {
makeSet(Nodes); // 注意：不应有重复的node
}
bool isInSameSet(const Node &a, const Node &b) {
return (findRootUnRecur(a) == findRootUnRecur(b));
}
void Union(const Node &a, const Node &b) {
Node rootA = findRootUnRecur(a);
Node rootB = findRootUnRecur(b);
if (rootA != rootB) {
int sizeA = sizeMap[rootA];
int sizeB = sizeMap[rootB];
if (sizeA <= sizeB) {
fatherMap[rootA] = rootB;
sizeMap[rootB] = (sizeA + sizeB);
}
else {
fatherMap[rootB] = rootA;
sizeMap[rootA] = (sizeA + sizeB);
}
}
}
private:
void makeSet(const vector<Node> &Nodes) {
fatherMap.clear();
sizeMap.clear();
for (auto node : Nodes) {
fatherMap[node] = node;
sizeMap[node] = 1;
}
}
Node findRootRecur(Node node) {
Node father = fatherMap[node];
if (father != node) {
father = findRootRecur(father);
}
fatherMap[node] = father;
return father;
}
Node findRootUnRecur(Node node) {
stack<Node> stk;
Node cur = node;
Node parent = fatherMap[cur];
while (cur != parent) {
stk.push(cur);
cur = parent;
parent = fatherMap[cur];
}
while (!stk.empty()) {
fatherMap[stk.top()] = parent;
stk.pop();
}
return parent;
}
map<Node, Node> fatherMap; // key ：child， value ：parent
map<Node, int> sizeMap; // key ：当前结点， value ：当前结点所在的集合一共有多少个结点
};
int main() {
const int N = 5;
vector<Node> Nodes = { Node(1), Node(2), Node(3), Node(4), Node(5) };
UnionFindSet disjoin_set(Nodes);
int a, b, cnt = 0;
cout << "开始查询：请输入元素A和元素B：";
while (cin >> a >> b) {
if (disjoin_set.isInSameSet(a, b))
cout << "元素a - " << a << ", 元素b - " << b << "：在同一个集合中\n";
else
cout << "元素a - " << a << ", 元素b - " << b << "：不在同一个集合中\n";
if (cnt++ > 2)
break;
cout << "\n开始查询：请输入元素A和元素B：";
}
cnt = 0;
cout << "\n开始合并：请输入合并元素A和元素B：";
while (cin >> a >> b) {
disjoin_set.Union(a, b);
cout << "元素a - " << a << ", 元素b - " << b << "：所在集合已合并\n";
if (cnt++ > 1)
break;
cout << "\n开始合并：请输入元素A和元素B：";
}
cnt = 0;
cout << "\n开始查询：请输入元素A和元素B：";
while (cin >> a >> b) {
if (disjoin_set.isInSameSet(a, b))
cout << "元素a - " << a << ", 元素b - " << b << "：在同一个集合中\n";
else
cout << "元素a - " << a << ", 元素b - " << b << "：不在同一个集合中\n";
if (cnt++ > 3)
break;
cout << "\n开始查询：请输入元素A和元素B：";
}
return 0;
}
二、岛问题
题目描述
一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右四个位置相连，如果有一片1连在一起，这个部分叫做一个岛，求一个矩阵中有多少个岛？
A：三个岛
2.1 解法1：单CPU单内存
两层for循环，每遍历一个点，就调用一次感染函数，
- 感染函数在传入一个下标时，会把属于一块的1全部变为2，感染完成后，岛数量+1
- 然后遍历下一个点，
如果它不为1（可能是2或者0），则遍历下一个。
如果它为1，则继续调用感染函数
重复上面的步骤直到遍历结束。
2.2 测试结果及代码
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <ctime>
using namespace std;
void printArray(const vector<vector<int>> &binaryArray) {
cout << binaryArray.size() << "行 * " << binaryArray[0].size() << "列矩阵：\n";
for (size_t i = 0; i < binaryArray.size(); ++i) {
for (size_t j = 0; j < binaryArray[0].size(); ++j) {
cout << binaryArray[i][j] << " ";
}
cout << endl;
}
}
void generateArray(vector<vector<int>> &binaryArray) {
for (size_t i = 0; i < binaryArray.size(); ++i) {
for (size_t j = 0; j < binaryArray[0].size(); ++j) {
binaryArray[i][j] = rand() % 2;
}
}
}
class Solution {
public:
int countIsLands(vector<vector<int>> &binaryArray) {
int res = 0;
int row = binaryArray.size();
int col = binaryArray[0].size();
for (size_t i = 0; i < row; ++i) {
for (size_t j = 0; j < col; ++j) {
if (binaryArray[i][j] == 1) {
res++;
infect(binaryArray, i, j, row, col);
}
}
}
return res;
}
private:
void infect(vector<vector<int>> &binaryArray, int i, int j, int row, int col) {
if (i < 0 || j < 0 || i >= row || j >= col || binaryArray[i][j] != 1)
return;
binaryArray[i][j] = 2;
infect(binaryArray, i - 1, j, row, col);
infect(binaryArray, i + 1, j, row, col);
infect(binaryArray, i, j - 1, row, col);
infect(binaryArray, i, j + 1, row, col);
}
};
int main() {
srand(time(NULL));
int test_cnt = 5;
Solution s;
for (int i = 0; i < test_cnt; ++i) {
int row = rand() % 2 + 3;
int col = rand() % 2 + 3;
vector<vector<int>> binaryArray(row);
for (int i = 0; i < row; ++i)
binaryArray[i].resize(col);
generateArray(binaryArray);
printArray(binaryArray);
cout << "有 " << s.countIsLands(binaryArray) << " 个岛\n\n";
}
return 0;
}
解法2：使用并查集多任务计算
思路：
将矩阵分块，分别统计出岛的数量，然后用适当的合并逻辑求解出正确的岛的数量。
显然这是比解法1快的。
先看分两块的情况：
可以看到，上面出现了判断两个元素所在的集合是否属于同一个，用并查集非常合适
好，那么切成很多块的时候也是一样的，需要统计块内的岛信息及块四个边界的信息即可。
这样，并行计算的框架就出来了。
于是，合并的时候就跟感染时差不多，上下左右合并，逐个遍历。