D. Secret Passwords
题解
想象一个一边是26个小写字母节点,一边是n个字符串节点的图,将每个字符串和其包含的字母之间连一条边,最后求整个图的连通分量个数,并查集。
代码
#include <algorithm>
#include <iostream>
#include <set>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;
constexpr int MAXN = 1e6 + 10;
int fa[MAXN];
int vis[27];
void init(int n) {
for (int i = 0; i <= n; i++)fa[i] = i;
}
int findr(int x) {
if (fa[x] == x)return x;
else return fa[x] = findr(fa[x]);
}
void merge(int x, int y) {
int xr = findr(x);
int yr = findr(y);
if (xr != yr)fa[xr] = yr;
}
int main(int argc, char **argv) {
int n;
string s;
cin >> n;
init(MAXN);
for (int i = 0; i < n; i++) {
cin >> s;
for (auto c : s) { merge(i, c + n - 'a'); vis[c - 'a'] = 1; }
}
set<int>ans;
for (int i = n; i < n + 26; i++)
if (vis[i - n] && ans.find(findr(i)) == ans.end())ans.insert(findr(i));
cout << ans.size() << endl;
return 0;
}