集合与并查集

集合与并查集

mi0e

January 31, 2023

835 views

No comments

1815 words

算法

# 集合

```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;

int son[N][26], cnt[N], idx;
int n;

void insert(string 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]++;
}

int query(string 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(){
	cin >> n;
	while(n--){
		char op;
		string str;
		cin >> op >> str;
		if(op == 'I') insert(str);
		else printf("%d\n", query(str)); 
	}

return 0;
}
```

## 洛谷P8306 题目描述

给定 $n$ 个模式串 $s_1, s_2, \dots, s_n$ 和 $q$ 次询问，每次询问给定一个文本串 $t_i$，请回答 $s_1 \sim s_n$ 中有多少个字符串 $s_j$ 满足 $t_i$ 是 $s_j$ 的**前缀**。

一个字符串 $t$ 是 $s$ 的前缀当且仅当从 $s$ 的末尾删去若干个（可以为 0 个）连续的字符后与 $t$ 相同。

输入的字符串大小敏感。例如，字符串 `Fusu` 和字符串 `fusu` 不同。

## 输入格式

**本题单测试点内有多组测试数据**。

输入的第一行是一个整数，表示数据组数 $T$。

对于每组数据，格式如下：
第一行是两个整数，分别表示模式串的个数 $n$ 和询问的个数 $q$。
接下来 $n$ 行，每行一个字符串，表示一个模式串。
接下来 $q$ 行，每行一个字符串，表示一次询问。

## 输出格式

按照输入的顺序依次输出各测试数据的答案。
对于每次询问，输出一行一个整数表示答案。

## 样例 #1

### 样例输入 #1

```
3
3 3
fusufusu
fusu
anguei
fusu
anguei
kkksc
5 2
fusu
Fusu
AFakeFusu
afakefusu
fusuisnotfake
Fusu
fusu
1 1
998244353
9
```

### 样例输出 #1

```
2
1
0
1
2
1
```

## 提示

### 数据规模与约定

对于全部的测试点，保证 $1 \leq T, n, q\leq 10^5$，且输入字符串的总长度不超过 $3 \times 10^6$。输入的字符串只含大小写字母和数字，且不含空串。

### 说明

std 的 IO 使用的是关闭同步后的 cin/cout，本题不卡常。

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 3 * 1e6 + 10, M = 65;

char str[N];
int son[N][M], cnt[N], idx;
int t, n, q;

void insert(char st[]){
    int p = 0, u;
    for (int i = 0; st[i]; i++) {
        int u;
        if (st[i] >= 'a' && st[i] <= 'z') u = st[i] - 'a' + 37;
        else if (st[i] >= 'A' && st[i] <= 'Z') u = st[i] - 'A' + 10;
        else u = st[i] - '0';
    
        if (!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
        cnt[p]++;
    }  
}

int query(char st[]){
    int p = 0, u;
    for (int i = 0; st[i]; i++) {
        if (st[i] >= 'a' && st[i] <= 'z') u = st[i] - 'a' + 37;
        else if (st[i] >= 'A' && st[i] <= 'Z') u = st[i] - 'A' + 10;
        else u = st[i] - '0';
    
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
  
    return cnt[p];
}

int main(){
    scanf("%d", &t);
  
    while (t--) {
		// 重点，使用memset会tle
        for (int i = 0; i <= idx; i++)
            for (int j = 0; j < M; j++) son[i][j] = 0;
        for (int i = 0; i <= idx; i++) cnt[i] = 0;
        idx = 0;
    
        scanf("%d%d", &n, &q);
    
        while (n--) {
            scanf("%s", str);
            insert(str);
        }
    
        while (q--) {
            scanf("%s", str);
            int c = query(str);
            printf("%d\n", c);
        }
    }
  
    return 0;
}
```

# 并查集

`p[x] = root` 数组存放根节点信息

```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 10010;

int p[N], n, m;

int find(int 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--){
		int z, x, y;
		scanf("%d%d%d", &z, &x, &y);
		if(z == 1) p[find(x)] = find(y);
		else{
			if(find(x) == find(y)) printf("Y\n");
			else printf("N\n");
		}
	}

return 0;
}
```

Last modification：February 26, 2023