CF1263D Secret Passwords 题解

题目链接：CF1263D Secret Passwords

题意：

给定$n$个字符串

• 如果存在一个或多个字母同时在字符串$a$和$b$中出现 这$a$和$b$就被分在同一组
• 如果$a$和$c$在同一组 $b$和$c$在同一组 则$a$和$b$也在同一组

问所有的字符串最后被分成几组。

输入格式:

The first line contain integer $n (1 \le n \le 2 \times 10^5)$ — number of passwords in the list. Next $n$ lines contains passwords from the list – non-empty strings $s_i$ , with length at most $50$ letters. Some of the passwords may be equal.

It is guaranteed that the total length of all passwords does not exceed $10^6$ letters. All of them consist only of lowercase Latin letters.

输出格式：

In a single line print the minimal number of passwords, the use of which will allow guaranteed to access the system.

水水水。注意到只要有一个字符相同就是同一组的。

例如 $\tt{a},\tt{b}$ 在一个字符串中出现，那所有有 $\tt{a,b}$ 的串都跟它是一个组的了。

我们也可以认为 $\tt{a,b}$ 是一组的，考虑用一个并查集维护哪些字母是一组的。

最后的答案就是连通块的个数。时间复杂度 $\mathcal{O}(\sum |s|)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5+15))

char s[N];
int n,stk[26],vis[26],f[26];
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
void merge(int u,int v) { f[find(u)] = find(v); }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=26; i++) f[i] = i;
    for(int i=1,len; i<=n; i++)
    {
        cin >> s; len = strlen(s);
        for(int j=0; j<26; j++) stk[j] = 0;
        for(int j=0; j<len; j++)
            ++stk[s[j] - 'a'],vis[s[j] - 'a' + 1] = 1;
        for(int j=0,lst=0; j<26; j++)
        {
            if(!stk[j]) continue;
            if(!lst) lst = j+1;
            else merge(lst,j+1), lst = j+1;
        }
    }
    int res = 0;
    for(int i=1; i<=26; i++) if(vis[i] && f[i] == i) ++res;
    cout << res << '\n';
    return 0;
}