数据结构¶

Trie¶

Trie字符串统计¶

STL-map做法

/**
 * @Date  2023/4/22 18:25
 */

#include <iostream>
#include <map>
using namespace std;

map<string, int> m;
int main() {
    int n;
    cin >> n;
    while (n -- ) {
        char c;
        string str;
        cin >> c >> str;
        if (c == 'I') {
            m[str] ++;
        } else {
            cout << m[str] << endl;
        }
    }
    return 0;
}

并查集¶

并查集：

1、将两个集合合并

2、询问两个元素是否在一个集合中

基本原理：

每个集合用一棵树来表示。树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]表示x的父节点

一些问题：

如何判断树根：if (p[x] == x)
如何求x的集合编号：while(p[x] != x) x = p[x];
如何合并两个集合：p[x] 是x的集合编号，p[y]是y的集合编号。p[x] = y

优化：路径压缩