1263 - D. Secret Passwords (并查集)

红太狼 2021-07-16 23:20 300阅读 0赞

[题目][Link 1]

思路：从答案上来看我们可以知道密码数最多只有26种即26个字母，然后根据可以等效的的密码(即直接或间接拥有相同的字母)，我们让可以等效的密码放在一个集合里(对每个密码让每一个字母与第一个字母连边构成一个连通图（并查集）)，然后最后的集合数即为答案。

Code:

#include<iostream>
    #include<string>
    #include<map>
    #include<algorithm>
    #include<memory.h>
    #include<cmath>
    #define pii pair<int,int>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 2e5 + 5;
    string str;
    int f[30];
    int book[30];
    
    int getf(int n)
    { 
    	if (f[n] == n)return n;
    	return f[n] = getf(f[n]);
    }
    
    void merge(int a, int b)
    { 
    	if (getf(a) != getf(b))f[getf(b)] = a;
    }
    
    int main()
    { 
    	int n;cin >> n;
    	for (int i = 1;i <= 26;i++) f[i] = i;
    	for (int i = 1;i <= n;i++)
    	{ 
    		cin >> str;int a = str[0] - 'a' + 1;book[a] = 1;
    		for (int j = 1;j < str.size();j++)
    		{ 
    			int b = str[j] - 'a' + 1;
    			book[b] = 1;
    			merge(a, b);
    		}
    	}
    	int sum = 0;
    	for (int i = 1;i <= 26;i++)if (i == f[i]&&book[i])sum++;
    	cout << sum << endl;
    }

[Link 1]: https://codeforces.ml/contest/1263/problem/D

发表评论取消回复

表情：

评论列表（有 0 条评论，300人围观）

还没有评论，来说两句吧...

相关阅读

相关并查集 Ⅱ

\[poj 1611\] ([http://poj.org/problem?id=1611][http_poj.org_problem_id_1611]) 题目描述： T

古城微笑少年丶/ 2022年08月03日 14:35/ 0 赞/ 259 阅读

相关并查集

并查集JAVA版框架并查集是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作： \--查询元素a和元素b是否属于同一组

落日映苍穹つ/ 2022年06月16日 12:44/ 0 赞/ 297 阅读

相关并查集

这个文章是几年前水acm的时候转的, 当时也不知道作者是谁, 要是有人知道的话说一下吧并查集是我暑假从高手那里学到的一招，觉得真是太精妙的设计了。以前我无法解决的

港控/mmm°/ 2022年06月13日 14:13/ 0 赞/ 280 阅读

相关并查集

> 题目 > 某学校近期要组织全校同学出去参加某项活动，由于人数众多，学校决定让同学们自行组队，以小组为单位进行活动。假设学校一共n个同学，每个同学有一个唯一的数字作为标签

Myth丶恋晨/ 2022年06月08日 09:24/ 0 赞/ 294 阅读

相关并查集

森林: 森林是由若干棵互不相交的树组成,两棵树分别独立,没有交集 ![20181112082744488.png][] 并查集: 并查集的结构和森林十分相似,是

Love The Way You Lie/ 2022年04月17日 02:27/ 0 赞/ 349 阅读

相关并查集

来看一个实例，[杭电1232畅通工程][1232] 首先在地图上给你若干个城镇，这些城镇都可以看作点，然后告诉你哪些对城镇之间是有道路直接相连的。最后要解决的是整幅图的连通性

我就是我/ 2022年03月29日 10:58/ 0 赞/ 348 阅读

相关并查集

例题： ![输入样例][20190805122001677.png] 输入样例，第一行为一个整数n，代表有n台电脑，编号1-n；接下来进行一系列操作，当输入‘c’时，判

Dear 丶/ 2021年11月11日 08:04/ 0 赞/ 374 阅读

相关并查集

一、算法解释用于解决一些有N个元素的集合应用问题。 1、将每个元素初始化为自身单独成为一个集合。用p\[i\]的值表示该元素所在集合。 ![这里写图片描述][S

桃扇骨/ 2021年09月14日 02:56/ 0 赞/ 453 阅读

相关 1263 - D. Secret Passwords (并查集)

[题目][Link 1] 思路：从答案上来看我们可以知道密码数最多只有26种即26个字母，然后根据可以等效的的密码(即直接或间接拥有相同的字母)，我们让可以等效的密码放在

红太狼/ 2021年07月16日 23:20/ 0 赞/ 301 阅读

相关并查集

并查集的作用就是快速判断两个元素是否在同一个集合中，快速将两个集合合并基本模板 include <iostream> include <a

比眉伴天荒/ 2021年06月22日 15:37/ 0 赞/ 546 阅读