图论基础知识 并查集/例题

并查集

学习记录自代码随想录

并查集可以解决的问题：

并查集常用来解决连通性问题。
判断两个元素是否在同一个集合里的时候，要想到用并查集。
并查集主要有两个功能：
1.将两个元素添加到一个集合中；
2.判断两个元素在不在同一个集合。

代码模板

int n = 1005;  // 节点数量大于题目要求一点即可
vector<int> father(n, 0);

// 并查集初始化
void init(){
	for(int i = 0; i < n; i++){
		father[i] = i;
	}
}

// 并查集寻根过程
int find(int u){
	return u == father[u] ? u : father[u] = find(father[u]);
}

// 判断u和v是否是同一个根,同一个根则在同一个集合
bool isSameRoot(int u, int v){
	u = find(u);
	v = find(v);
	return u == v;
}

// 将v-u这条边加入并查集
void join(int u, int v){
	u = find(u);
	v = find(v);
	// 同一个根则说明在同一个集合，不需要节点相连
	if(u == v) return;
	father[v] = u;
}

例题：20240410 Huawei机考

//2.相似图片分类
//小明想要处理一批图片，将相似的图片分类。他首先对图片的特征采样，得到图片之间的相似度，然后按照以下规则判断图片是否可以归为一类 :
//
//1)相似度 > 0表示两张图片相似，
//2)如果A和B相似，B和C相似，但A和C不相似。那么认为A和C间接相似，可以把ABC归为一类，但不计算AC的相似度
//3)如果A和所有其他图片都不相似，则A自己归为一类，相似度为0.
// 给定一个大小为NxN的矩阵M存储任意两张图片的相似度，
//M[i][j]即为第i个图片和第j个图片的相似度，请按照"从大到小”的顺序返回每个相似类中所有图片的相似度之和。
//
//解答要求
//时间限制 : C / C++ 1000ms, 其他语言 : 2000ms内存限制 : C / C++ 256MB, 其他语言 : 512MB
//
//输入
//第一行一个数N，代表矩阵M中有N个图片，下面跟着N行，每行有N列数据，空格分隔(为了显示整齐，空格可能为多个) 代表N个图片之间的相似度。
//约束：
//1.0 < N <= 900
//2.0 <= M[i][j] <= 100, 输入保证M[i][i] = 0, M[i][j] = M[j][i]
//输出
//每个相似类的相似度之和。格式为 : 一行数字，分隔符为1个空格。

//样例
//
//输入
//5
//0 0 50 0 0
//0 0 0 25 0
//50 0 0 0 15
//0 25 0 0 0
//0 0 15 0 0
//输出
//65 25

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <map>

using namespace std;

class Solution {
public:
	/*int n;
	Solution(int x) : n(x){}*/\
	// 初始化
	vector<int> init(vector<int>& father) {
		for (int i = 0; i < father.size(); i++) {
			father[i] = i;
		}
		return father;
	}
	// 查找根节点
	int find(int x, vector<int>& father) {
		return father[x] == x ? x : father[x] = find(father[x], father);
	}
	// 判断是否在一个集合中
	bool isSameRoot(int u, int v, vector<int>& father) {
		u = find(u, father);
		v = find(v, father);
		return u == v;
	}
	// 将u<----v边加入
	void join(int u, int v, vector<int>& father) {
		u = find(u, father);
		v = find(v, father);
		if (u == v) return;
		father[v] = u;
	}

	vector<int> getSimilarity(vector<vector<int>>& M, int N) {
		vector<int> father(N, 0);
		father = init(father);
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				if (M[i][j] > 0) {
					join(i, j, father);
				}
			}
		}
		map<int, vector<int>> root_set;
		for (int i = 0; i < N; i++) {
			root_set[find(i, father)].push_back(i);
		}
		vector<int> res;
		for (const auto& it : root_set) {
			int cnt = 0;
			for (int i = 0; i < it.second.size(); i++) {
				for (int j = i + 1; j < it.second.size(); j++) {
					cnt += M[it.second[i]][it.second[j]];
				}
			}
			res.push_back(cnt);
		}
		return res;
	}
};

int main() {

	int N;
	cin >> N; cin.ignore();
	int temp = N;
	vector<vector<int>> M;
	while (temp--) {
		string line;
		getline(cin, line);
		vector<int> nums;
		istringstream iss(line);
		string k;
		while (iss >> k) {
			nums.push_back(stoi(k));
		}
		M.push_back(nums);
	}

	Solution sol;
	vector<int> res = sol.getSimilarity(M, N);
	for (int i = 0; i < res.size() - 1; i++) {
		cout << res[i] << ' ';
	}
	cout << res[res.size() - 1];

	return 0;
}