首页 > 其他 > 详细

Secret Passwords

时间:2020-07-27 16:07:17      阅读:66      评论:0      收藏:0      [点我收藏+]

并查集内容参考链接:https://blog.csdn.net/wmy0217_/article/details/104972191

代码参考:https://blog.csdn.net/Luoriliming/article/details/103325459

int n,fa[50];
char s[1001];
int vis[200001], ans;
int fin(int x){
    return x == fa[x] ? x : fa[x] = fin(fa[x]);
}
int main() {
    cin >> n;
    for (int i = 1; i <= 30; i++) {
        fa[i] = i;  //各自为一个集合
    }
    for (int i = 1; i <= n; i++) {
        cin >> s;
        int l = strlen(s);
        for (int j = 0; j < l - 1; j++) {
            vis[s[j] - a + 1] = 1;
            int x = fin(s[j] - a + 1), y = fin(s[j + 1] - a + 1);
            if (x != y) {
                fa[x] = y;  //若在一个单词内,祖宗结点不一致,则合并祖宗结点
            }
            vis[s[l - 1] - a + 1] = 1;
        }
    }
    for (int i = 1; i <= 26; i++){
        if (vis[i] && fa[i] == i) {  //最后在n个单词中,只要单词与单词之间有字母相同,则祖宗结点一致
            ans++;  //统计祖宗结点未变的个数并且已访问的
        }
    }
    cout << ans << endl;
    return 0;
}

 

Secret Passwords

原文:https://www.cnblogs.com/0211ji/p/13384925.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!