方法一:Y总方法:并查集+一次遍历
#include <iostream>
#include <string>
using namespace std;
const int N = 2e5 + 10;
int fa[N];
int id[26];
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int res = n;
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
for (int j = 0; s[j]; j++) {
int x = s[j] - 'a';
if (!id[x]) {
id[x] = i;
}
else {
if (find(i) != find(id[x])) {
fa[find(i)] = find(id[x]);
res--;
}
}
}
}
cout << res << endl;
return 0;
}
方法二:我的方法:并查集+26次遍历
将每一个字符串等价于一个字符串集合,再将该集合化为int
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
unordered_map<int, int> fa;
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
int x = 0;
for (int i = 0; s[i]; i++) {
x |= 1 << (s[i] - 'a');
}
fa[x] = x;
}
for (int i = 0; i < 26; i++) {
int fx = -1;
for (auto& [x, _] : fa) { // 枚举每一个字符串
if ((x >> i) & 1) {
if (fx == -1) { // 如果该字母第一次出现,则fx = -1
fx = find(x); // 另所有包含字母i的字符串的祖先为fx
}
else {
fa[find(x)] = fx;
}
}
}
}
int res = 0;
for (auto& [k, v] : fa) {
if (k == v) {
res++;
}
}
cout << res << endl;
return 0;
}