codeforces div2 603 D. Secret Passwords(并查集)

时间:2022-06-28 11:42:55

题目链接:https://codeforces.com/contest/1263/problem/D

题意:有n个小写字符串代表n个密码,加入存在两个密码有共同的字母,那么说这两个密码可以认为是同一个集合,可以互相破解,先求有多少个不同集合的密码

思路:简单的并查集。首先一共有26个字母,对于每个密码,我们合并其所涵盖的字母,例如密码1:abcd,那么abcd合并起来,含有abcd的任意密码都同属于一个集合,所有我们把n个密码串先做一次合并。最终再扫一遍所有的密码串,用set维护集合的个数,最终输出set集合的大小即可。

代码:

 #include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn =2e5+;
int fa[];
void init(){
for(int i = ;i<=;i++){
fa[i] = i;
}
}
int find(int x){
if(fa[x] == x) return x;
else return fa[x] = find(fa[x]);
}
void unite(int x,int y){
int tx = find(x),ty = find(y);
if(tx == ty) return ;
fa[y] = tx;
}
int main(){
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
int n;
cin>>n;
init();
set<int> ss;
vector<string> v;
while(n--){
string s;
cin>>s;
v.push_back(s);
int t = s[]-'a'+;
for(int i = ;i<s.length() ;i++){
int cur = s[i]-'a'+;
unite(t,cur);//合并当前字符串的所有字母
}
}
for(int i = ;i<v.size() ;i++){
for(int j =;j<v[i].length();j++){
ss.insert(find(v[i][j]-'a'+));//扫所有字符串的所有字母,判断是否是同一父亲
}
}
cout<<ss.size();
return ;
}