题目：字符串归类

发现字符串长度总数不大，因此把每个字符串有的字母分离，存放到桶中，再枚举合并即可，时间复杂度O(len)

赛时代码：

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

const int N=2e5+5;

using namespace std;

int n,fa[N],cnt[N],t[30],tt[30][N],ret;

char s[N][55];

int find(int x)

{

    if(x==fa[x])

        return x;

    return fa[x]=find(fa[x]);

}

bool merge(int x,int y)

{

    int r1=find(x),r2=find(y);

    if(r1==r2)

        return 0;

    fa[r1]=r2;

    return 1;

}

int main()

{

    scanf("%d",&n);

    ret=n;

    for(int i=1;i<=n;i++)

    {

        fa[i]=i;

        scanf("%s",s[i]+1);

        int m=strlen(s[i]+1);

        memset(t,0,sizeof(t));

        for(int j=1;j<=m;j++)

            if(!t[s[i][j]-'a'])

                t[s[i][j]-'a']=1,tt[s[i][j]-'a'][++cnt[s[i][j]-'a']]=i;

    }

    for(int i=0;i<26;i++)

        for(int j=2;j<=cnt[i];j++)

            if(merge(tt[i][j],tt[i][j-1]))

                ret--;

    printf("%d\n",ret);

    return 0;

}

巴特西

2022春每日一题：Day 14

题目：字符串归类

最新文章

热门文章