Union-Find^[1]

• 初始化时每个元素各成一个集合
• fa[i] 即指向 ---〉i 所在集合的代表元素

int fa[MAXN];
void init(int n){
	for (int i = 1; i <= n; ++i)
		fa[i] = i;
}
Copy

• 每个集合只能有一个代表元素
• 故查询时回溯至找到代表元素是停止
• find(x) 应定义为x元素的所在集合的代表元素

int find(int x){
	if(fa[x] == x)
		return x;
	else
		return find(fa[x]);
}
Copy

• 合并的基本逻辑是另一个集合的代表元素变成另一个集合的代表元素
• 分解操作
  • find(i) i元素所在集合的代表元素
  • fa[i] 即指向 ---〉集合的代表元素
  • find(j) j元素所在集合代表元素

找到i元素所在集合的代表元素 使该元素的代表元素指向 j元素的代表元素

void merge(int i, int j){
	fa[find(i)] = find(j);
}
Copy

• 令所有节点都指向同一个父节点

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]));
}
Copy

• 初始化

void init(int n){
	for (int i = 1; i <= n; ++i){
		fa[i] = i;
		rank[i] = 1;
	}
}
Copy

• 合并

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
	}
Copy

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]++;	
	}
	};
Copy

#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;

}

  

## 婴儿的名字

  

Copy

每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。有些名字有多种拼法，例如，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)"]

Copy

提示：

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;

}

};

Copy