trie树
#include <iostream>
using namespace std;
const int N = 1000010;
int son[N][26],cnt[N],idx;
//明确前面两个数组以及idx的含义
//我们把son这个二维数组看成一个字典树
//本题要求26个字母，所以我们每个节点里面最多有26个儿子节点
//而我们本题要求字符串长度是100000个，所以son数组的N代表有100000层，对应的就是字符串长度
//为什么这样就可以呢，因为我们查找的字符串（只有26个字母）在查找的时候想象成树
//每次面临26种选择（26个字母）(也有点组合的意思)，选择一种和当前匹配的，没有就说明没有匹配的
//idx是什么呢，我们怎么用数组来模拟的呢，我们怎么算是创建过这个节点了，我们son数组的元素为1
//就代表我们创建了这个节点，如果遇到这个节点之后我们就可以直接往下走，如果没有遇到，我们就
//不往下走,先创建在走，创建的过程就是idx++,就是走到当前元素为1时说明创建过了
//cnt数组表示以当前节点的值为终点的字符串个数
char str[N];
void insert(char str[])
{
int p = 0;//p代表我们当前走到哪个位置了（把数组抽象成一棵树）
for(int i = 0; str[i] != '\0';i++)//枚举插入的字符串，枚举的字符串抽象成路径
{
int u = str[i] - 'a';//映射到数组里，son数组一维数组的下标0代表的是a，1是b
if(son[p][u] == 0) son[p][u] = ++idx;//每次进入判断是否创建过当前值的节点
p = son[p][u];//走到下一层
}
cnt[p]++;//当前下标为终点的字符串个数++
}
int inquire(char str[])
{
int p = 0;
for(int i = 0; str[i] != '\0';i++)
{
int u = str[i] - 'a';
if(!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}
int main()
{
int n;
cin>>n;
for(int i = 0;i < n;i++)
{
char chose[2];
cin>>chose>>str;
if(chose[0] == 'I')
{
insert(str);
}
else
{
printf("%d\n",inquire(str));
}
}
return 0;
}
并查集
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
//本题是模板题，所以我们先理解这道题的模板是什么
//本题的模板是并查集，那什么是并查集呢，其实你可以想象成一个树
//我们的字符串都是通过递归去搜索的，跟字典树类似
//但是并查集强在归并和询问的操作近乎O(1)的时间复杂度,可以快速将两个集合
//合并和快速查两个集合是否在同一个集合
//并查集的基本原理是什么呢，基本原理就是每个集合我们看成一颗小树，一颗大树里可能包含小树
//比方说一个字符串是一个集合，那么这棵大树可能就有好多字符串集合，
//那我们并查集是怎么快速实现合并和查询的呢，这就要说到并查集的编号了
//我们怎么去查找到这个集合呢，我们肯定得让他的根节点跟孩子节点编号不一样，我们才能找到
//我们的集合，在此我们设置P[x]为节点的编号，而p[x] == x 是根节点的编号
//我们的p[x]代表的是当前节点的父节点
//1.如何判断根节点 if(p[x] == x)
//2.如何从孩子节点求根节点的编号while(p[x]!=x) x = p[x];
//3.如何合并两个集合，假设编号是p[X],P[Y],前面提到过的我们抽象成一颗树，这棵树
//合并只需要把一个根节点作为另一个根节点的父节点即可
//在此，我们还需要优化一下，路径压缩法,等于说第一次查询过这个集合之后下次查询就是O（1)的
//时间复杂度,为什么呢，想象一下一棵树的高度只有2，根节点只有1个，这时我们查询集合的所以元素的话
//我们就只需要遍历这个集合就元素就行，不需要再去递归好几层了
//并查集模板最关键的点是在于写出find操作
const int N = 1000010;
int p[N];
int find(int x)//返回要查找的元素的集合,递归查找
{
if(p[x] != x) p[x] = find(p[x]);//如果父节点不是根节点，那么就把接力棒给父节点
//让父亲节点去找
return p[x];//找到了就返回
}
int main()
{
int n, m;
cin >> 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] == 'Q')
{
if (find(a) == find(b)) printf("Yes\n");
else printf("No\n");
}
else if(op[0] == 'M')
{
p[find(a)] = find(b);//找到a集合的根节点，把a集合的根节点查到b集合的根节点
}
}
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510000;
int p[N],d[N];
int n,m;
int find(int x)//路径压缩
{
if(p[x] != x)//不是根节点的话
{
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}
int main()
{
cin>>n>>m;
for(int i = 1;i <= N;i++)
{
p[i] = i;
}
int cnt = 0;
for(int i = 1;i <= m;i++)
{
int op,a,b;
cin>>op>>a>>b;
if(a > n || b > n)
{
cnt++;
continue;
}
int pa = find(a);
int pb = find(b);
if(op == 1)
{
if(pa == pb && (d[a] - d[b]) % 3){
//是在同一个集合的话，判断是否是同类
//不是同类res++，是同类不用管
cnt++;
}
else if(pa != pb){
//不在同一个集合，判断是否同类
//先建立两个集合的集合关系，为什么建立两个呢
//因为能find找到说明必有根节点
//本题根节点肯定存在，就算只有两个节点
//我们也看成两个集合
p[p[a]] = pb;//让x集合的根节点作为y集合的根节点的孩子
//节点
//建立之后还得更新一下距离关系，第一次进入的话其实
//并没有建立集合，也就是刚好是说了第一句话的时候
//第一句不同的x和y或者两个相同的x或者y我们默认为真话，
//默认为x和y同类并且建立关系（同类关系）
//所以x和y分别到当前建立好集合关系
//的根节点的距离一定要相等，所以距离
//就是d[x] + ？= d[y]，这个问好是根节点到px的距离
d[pa] = d[b] - d[a];
}
}
else
{
if(pa == pb && (d[a] - d[b] -1) %3){
//在同一个集合
//并且不是x 吃 y的关系
//c++中-n % n等于0
cnt++;
}
else if(pa != pb){
//不是同一个集合的话，那么我们默认为
//真话，x能吃掉y
p[p[a]] = pb;
//维护距离使得x能吃掉y
d[pa] = d[b] - d[a] + 1;
}
}
}
cout<<cnt<<endl;
return 0;
}
