[Acwing] 4304. 字符串归类 并查集

前言

传送门 :

题意

题目大致意思是 ，如果两个字符串中有相同的字母那么就是同一类 ,

如果字符串 a a a和字符串 b b b是同一类,那么是满足传递的

思路

一共26个字母,显然在同一个字符串中的肯定是同一类的,所以我们可以将思考从字符串转到单个字母上面。这样子我们只需要对单个字母进行并查集操作即可。

CODE

const int N  = 27;
int p[N];
int st[N];

int find(int x){
	if(x!=p[x])return p[x] =  find(p[x]);
	return p[x];
}
void solve()
{
	int n;cin>>n;
	for(int i=0;is;
		int x =  s[0] - 'a';
		st[x] =  1;
		int fx =  find(x);
		
		
		for(int j = 1;j