【数据结构1-3】集合【持续更新中】

题目链接：P1551 亲戚 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include 
using namespace std;
int fa[5005], Rank[5005];

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

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;
	cin >> n >> m >> p;
	for (int i = 1; i <= n; i++) {
		fa[i] = i;
		Rank[i] = 1;
	}
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		merge(x, y);
	}
	for (int i = 0; i < p; i++) {
		cin >> x >> y;
		if (find(x) == find(y)) {
			cout << "Yes" << endl;
		} else {
			cout << "No" << endl;
		}
	}
	return 0;
}

参考博客：算法学习笔记(1) : 并查集 - 知乎 (zhihu.com) 

error: reference to 'rank' is ambiguous_荷叶田田-CSDN博客

题目链接：P1536 村村通 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include 
using namespace std;
int fa[1010], n, m;

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

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

int main() {
	while (true) {
		cin >> n;
		if (n == 0) {
			return 0;
		}
		cin >> m;
		for (int i = 1; i <= n; i++) {
			fa[i] = i;
		}
		int x, y;
		for (int i = 0; i < m; i++) {
			cin >> x >> y;
			merge(x, y);
		}
		int ans = 0;
		for (int i = 1; i <= n; i++) {
			if (i == find(i)) {
				ans++;
			}
		}
		ans--;
		cout << ans << endl;
	}
}

题目链接：P3370 【模板】字符串哈希 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include 
#include 
#include 
using namespace std;
long long f[100010];

unsigned long long Hash(string s) {
	unsigned long long cnt = 0;
	for (int i = 0; i < s.size(); i++) {
		cnt = 233 * cnt + (unsigned long long)s[i];
	}
	return cnt;
}

int main() {
	int n, ans = 1;
	cin >> n;
	string s;
	for (int i = 0; i < n; i++) {
		cin >> s;
		f[i] = Hash(s);
	}
	sort(f, f + n);
	for (int i = 1; i < n; i++) {
		if (f[i] != f[i - 1]) {
			ans++;
		}
	}
	cout << ans;
	return 0;
}