题意
给n个字符串,两个字符串之间如果有相同的字符,那么两个就等价,等价关系可以传递,问最后有多少个等价类。
分析
- 考虑并查集或者dfs联通块,如果是并查集的话,对于当前字符串的某个字符,肯定要和这个字符在前面出现的某个字符串合并起来,所以维护每个字符的最后一次出现位置即可。
- 如果是dfs找联通块,建图就是把26个字符看成26个点,然后字符串分别连向这些字符,最后从字符节点dfs标记。
代码
- dfs
#include <bits/stdc++.h>
using namespace std;
const int N=2e6+50;
int n;
char s[55];
struct Edge{
int v,next;
}e[N*2];
int cnt,head[N];
int ind[N];
void init(){
cnt=0;
memset(head,-1,sizeof(head));
}
void add(int u,int v){
e[cnt]=Edge{v,head[u]};
head[u]=cnt++;
e[cnt]=Edge{u,head[v]};
head[v]=cnt++;
}
int v[30],vis[N];
void dfs(int u){
vis[u]=1;
for(int i=head[u];i!=-1;i=e[i].next){
int v=e[i].v;
if(vis[v]){
continue;
}
dfs(v);
}
}
int main(){
scanf("%d",&n);
init();
for(int i=1;i<=n;i++){
scanf("%s",s+1);
int len=strlen(s+1);
memset(v,0,sizeof(v));
for(int j=1;j<=len;j++){
if(!v[s[j]-'a'+1]){
ind[s[j]-'a'+1]++;
add(26+i,s[j]-'a'+1);
v[s[j]-'a'+1]=1;
}
}
}
int ans=0;
for(int i=1;i<=26;i++){
if(ind[i] && !vis[i]){
dfs(i);
ans++;
}
}
printf("%d\n",ans);
return 0;
}
- 并查集
#include <bits/stdc++.h>
using namespace std;
const int N=2e6+50;
int p[N];
int n;
char s[55];
int let[30];
void init(int n){
for(int i=1;i<=n;i++){
p[i]=i;
}
}
int find(int x){
return x==p[x]?p[x]:p[x]=find(p[x]);
}
int main(){
scanf("%d",&n);
init(n);
for(int i=1;i<=n;i++){
scanf("%s",s+1);
int len=strlen(s+1);
for(int j=1;j<=len;j++){
if(let[s[j]-'a'] && let[s[j]-'a']!=i){
int fa=find(let[s[j]-'a']);
int fb=find(i);
if(fa!=fb){
p[fa]=fb;
}
}
let[s[j]-'a']=max(let[s[j]-'a'],i);
}
}
int ans=0;
for(int i=1;i<=n;i++){
if(p[i]==i){
ans++;
}
}
printf("%d\n",ans);
return 0;
}