Skip to the content.

D. Secret Passwords

Link

题解

想象一个一边是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;
}