date: 2024-02-28
title: Union-Find
author:
- AllenYGY
status: DONE
tags:
- NOTE
- DataStructure
- UnionFind
- Algorithm
created: 2024-02-28
updated: 2024-05-31T01:00
publish: TrueUnion-Find
int fa[MAXN];
void init(int n){
for (int i = 1; i <= n; ++i)
fa[i] = i;
}
int find(int x){
if(fa[x] == x)
return x;
else
return find(fa[x]);
}
find(i) i元素所在集合的代表元素fa[i] 即指向 ---〉集合的代表元素find(j) j元素所在集合代表元素找到i元素所在集合的代表元素 使该元素的代表元素指向 j元素的代表元素
void merge(int i, int j){
fa[find(i)] = find(j);
}
int find(int x){
if(x == fa[x])
return x;
else{
fa[x] = find(fa[x]); //父节点设为根节点
return fa[x]; //返回父节点
}
}
int find(int x){
return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
void init(int n){
for (int i = 1; i <= n; ++i){
fa[i] = i;
rank[i] = 1;
}
}
void merge(int i, int j){
int x = find(i), y = find(j); // * 先找到两个根节点
if (rank[x] <= rank[y])
fa[x] = y;
else
fa[y] = x;
if (rank[x] == rank[y] && x != y)
rank[y]++; // * 如果深度相同且根节点不同，则新的根节点的深度+1
}
class Ufds {
private:
vector<int> parents;
vector<int> ranks;
public:
Ufds(int n) {
parents.resize(n);
ranks.resize(n);
for (int i = 0; i < n; i++) {
parents[i] = i;
ranks[i] = i;
}
}
int findSet(int a) {
if (parents[a] != a) {
parents[a] = findSet(parents[a]);
}
return parents[a];
}
void unionSets(int a, int b) {
a = findSet(a);
b = findSet(b);
if (a == b) return;
if (ranks[a] < ranks[b]) {
int temp = a;
a = b;
b = temp;
}
parents[b] = a;
ranks[a]++;
}
};
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
规定：
第一行：三个整数
以下
接下来
Yes 或 No。表示第
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6
Yes
Yes
No
#include <cstdio>
#define MAXN 5005
int fa[MAXN], rank[MAXN];
inline void init(int n)
{
for (int i = 1; i <= n; ++i)
{
fa[i] = i;
rank[i] = 1;
}
}
int find(int x)
{
return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
inline void merge(int i, int j)
{
int x = find(i), y = find(j);
if (rank[x] <= rank[y])
fa[x] = y;
else
fa[y] = x;
if (rank[x] == rank[y] && x != y)
rank[y]++;
}
int main()
{
int n, m, p, x, y;
scanf("%d%d%d", &n, &m, &p);
init(n);
for (int i = 0; i < m; ++i)
{
scanf("%d%d", &x, &y);
merge(x, y);
}
for (int i = 0; i < p; ++i)
{
scanf("%d%d", &x, &y);
printf("%s\n", find(x) == find(y) ? "Yes" : "No");
}
return 0;
}
## 婴儿的名字
每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。有些名字有多种拼法，例如，John 和 Jon 本质上是相同的名字，但被当成了两个名字公布出来。给定两个列表，一个是名字及对应的频率，另一个是本质相同的名字对。设计一个算法打印出每个真实名字的实际频率。注意，如果 John 和 Jon 是相同的，并且 Jon 和 Johnny 相同，则 John 与 Johnny 也相同，即它们有传递和对称性。
在结果列表中，选择 字典序最小 的名字作为真实名字。
示例：
输入：names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"], synonyms = ["(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"]
输出：["John(27)","Chris(36)"]
提示：
class Solution {
private:
unordered_map<string, string> parent;
unordered_map<string, int> frequency;
string find(string x) {
if (parent.find(x) == parent.end())
return x;
if (parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
void merge(string i, string j) {
string x = find(i);
string y = find(j);
if (x==y) return;
if (x < y) {
parent[y] = x;
frequency[x] += frequency[y];
frequency[y] = 0;
}
else{
parent[x]=y;
frequency[y]+=frequency[x];
frequency[x]=0;
}
}
public:
vector<string> trulyMostPopular(vector<string>& names, vector<string>& synonyms) {
// Parse and initialize frequencies
for (const string& name : names) {
int pos = name.find('(');
string nameStr = name.substr(0, pos);
int freq = stoi(name.substr(pos + 1, name.size() - pos - 2));
parent[nameStr] = nameStr;
frequency[nameStr] = freq;
}
// Process synonyms
for (const string& synonym : synonyms) {
int pos = synonym.find(',');
string name1 = synonym.substr(1, pos - 1);
string name2 = synonym.substr(pos + 1, synonym.size() - pos - 2);
merge(name1, name2);
}
// Build the result
vector<string> result;
for (auto& entry : frequency) {
string name = entry.first;
int freq = entry.second;
if (name == find(name)) {
string nameFreq = name + "(" + to_string(freq) + ")";
result.push_back(nameFreq);
}
}
return result;
}
};