算法学习08：Trie树（字典树）、并查集

---

---

前言

---

提示：以下是本篇文章正文内容：

一、Trie树（字典树）

---

---

例题：维护一个字符串集合，支持两种操作：
（1）向集合中插入字符串x
（2）询问一个字符串在集合中出现了多少次

---

---

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

char str[N];// 字符串 

//idx：表示当前结点 位置 
int son[N][26], cnt[N], idx;//下标是0的点，既是根节点，又是空节点

void insert(char str[])
{
	int p = 0;//从根节点开始 
	for(int i = 0; str[i]; i ++)
	{
		int u = str[i] - 'a';
		// 出现没有访问过的结点 
		if(!son[p][u]) son[p][u] = ++ idx;
		p = son[p][u];// 移动 
	}
	cnt[p] ++;// 字符串结尾 计数+1 
 } 
 
 int  query(char str[]) 
 {
 	int p = 0;
 	for(int i = 0; str[i]; i ++)
 	{
 		int u = str[i] - 'a';
 		if(!son[p][u]) return 0;// 中途匹配失败 
 		p = son[p][u]
	 }
	 return cnt[p];//找到最后了 
 }
 
 int main()
 {
 	int n;
	 scanf("%d", &n);
	 while(n --)
	 {
	 	char op[2];
	 	scanf("%s%s", op, str);
	 	if(op[0] == 'I') insert(str);// 向集合中插入字符串x
	 	else printf("%d\n", query(str));// 询问一个字符串在集合中出现了多少次
	  } 
 	return 0;
 }

---

---

二、并查集

1.例题1：合并 + 判断

---

---

---

---

例题：一共用n个数，编号是1~n，最开始每个数各自在一个集合中。
（1）将编号为a和b的两个数所在的集合合并
（2）询问编号为a和b的两个数是否在同一个集合中

---

---

#include <iostream>

using namespace std;

const int N = le5 + 10;

int n, m;
int p[N];

int find(int x)//返回x的祖宗结点 + 路径优化（递归） 
{
	if(p[x] != x) p[x] = find(p[x]);
	return p[x]; 
 } 
 
 int main()
{
	scanf("%d%d", &n, &m);
	
	for(int i = 1; i <= n; i ++) p[i] = i;// 数据输入 
		
	while(m --)
	{
		// 用 字符串 读取 字符 效果更好 
		// 可以避免读入空格 
		char op[2];
		int a, b;
		scanf("%s%d%d", op, &a, &b);
		
		if(op[0] == 'M') p[find(a)] = find(b);//合并集合 
		else
		{
			//判断a和b是否属于同一个集合 
			if(find(a) == find(b)) puts("Yes");
			else puts("No");
		}
	}
	return 0;
}

2.例题2：合并 + 判断 + 元素个数（连通图/块）

---

---

例题2：给定一个包含n个点（编号为1~n）的无向图，初始时，途中没有边。
现在有进行m个操作，操作有3种：
（1）在点a、b之间连一条边，a和b可能相等
（2）询问a、b是否在同一个连通块中
（3）询问点a所在连通块中 点的数量

---

---

#include <iostream>

using namespace std;

const int N = le5 + 10;

int n, m;
int p[N], size[N];//p：数据存储的地方 size：集合中元素的数量 

int find(int x)//返回x的祖宗结点 + 路径优化（递归） 
{
	if(p[x] != x) p[x] = find(p[x]);
	return p[x]; 
 } 
 
 int main()
{
	scanf("%d%d", &n, &m);
	
	for(int i = 1; i <= n; i ++) 
	{
		p[i] = i;
		size[i] = 1;// 每个都有 
	 } 
		
	while(m --)
	{
		// 用 字符串 读取 字符 效果更好 
		// 可以避免读入空格 
		char op[5];
		int a, b;
		scanf("%s", op);
		
		if(op[0] = 'C') 
		{
			scanf("%d%d", &a, &b);
			// 如果a、b不属于同一个集合，那么合并，size也要增加 
			if(find(a) == find(b)) continue;//1
			size[find(b)] += size[find(a)];//2
			p[find(a)] = find(b);
		}
		else if(op[1] == '1')
		{
			scanf("%d%d", &a, &b);
			if(find(a) == find(b)) puts("Yes");
			else puts("No");
		}
		else
		{
			scanf("%d", &a);
			printf("%d\n", size[find(a)]);
		}
	}
	return 0;
}

---

总结

提示：这里对文章进行总结：