学习记录自代码随想录
并查集常用来解决连通性问题。
判断两个元素是否在同一个集合里的时候,要想到用并查集。
并查集主要有两个功能:
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
#include
#include
#include
#include
#include
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;
}