D. Secret Passwords（并查集）

86 阅读 0 评论 57 点赞

我是靠谱客的博主无心火，最近开发中收集的这篇文章主要介绍D. Secret Passwords（并查集），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：Problem - 1263D - Codeforces

题意：

给定n个字符串。（1<=n<=2e5）（字符串长度不超过50）

如果存在一个或者多个字母同时出现在字符串a和字符串b中，那么a和b就被分到同一组。

如果a和c在同一组，b和c在同一组，则a和b也在同一组。

思路：

先初始化代表父节点的数组fa，接着输入字符串，并记录每个字符串中所含的字母，记录在数组a中，用历遍以及并查集的思想，将每组字符串的父节点定为最后一个字母，将各个字符串连接起来最后记录下父节点和原来相同的元素个数，便可以得到答案。

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int ma = 2e5 + 100;
int fa[ma];
string str[ma];
vector<int>a[110];
int find(int x)
{
    if (x == fa[x])
        return fa[x];
    return fa[x] = find(fa[x]);
}
int main()
{
    int n;
    cin >> n;
    int i,j;
    for (i = 1; i <= n; i++)
    {
        fa[i] = i;
    }
    for (i = 1; i <= n; i++)
    {
        cin >> str[i];
        for (j = 0; j < str[i].size(); j++)
        {
            a[str[i][j] - 'a'].push_back(i);
        }
    }
    for (i = 0; i < 26; i++)
    {
        for (j = 0; j < a[i].size(); j++)
        {
            int l = find(a[i][0]);//从第一个子节点开始
            int r = find(a[i][j]);
            if (l != r)
            {
                fa[l] = r;
            }
        }
    }
    int ans = 0;
    for (i = 1; i <= n; i++)
    {
        if (fa[i] == i)
        {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}