0%

二分图

一个图是二分图 当且仅当图中不含奇数环

染色法

o(m+n)
判断二分图

代码流程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int n;      // n表示点数
int h[N], e[M], ne[M], idx; // 邻接表存储图
int color[N]; // 表示每个点的颜色,-1表示未染色,0表示白色,1表示黑色

// 参数:u表示当前节点,c表示当前点的颜色
bool dfs(int u, int c)
{
color[u] = c;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (color[j] == -1)
{
if (!dfs(j, !c)) return false;
}
else if (color[j] == c) return false;
}

return true;
}

bool check()
{
memset(color, -1, sizeof color);
bool flag = true;
for (int i = 1; i <= n; i ++ )
if (color[i] == -1)
if (!dfs(i, 0))
{
flag = false;
break;
}
return flag;
}


匈牙利算法

最坏o(mn)
最大匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int n1, n2;     // n1表示第一个集合中的点数,n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx; // 邻接表存储所有边,匈牙利算法中只会用到从第一个集合指向第二个集合的边,所以这里只用存一个方向的边
int match[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N]; // 表示第二个集合中的每个点是否已经被遍历过

bool find(int x)
{
for (int i = h[x]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true;
if (match[j] == 0 || find(match[j]))
{
match[j] = x;
return true;
}
}
}

return false;
}

// 求最大匹配数,依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ )
{
memset(st, false, sizeof st);
if (find(i)) res ++ ;
}


最小生成树

prim算法 (稠密图)

朴素版prim算法 (常用)

代码短
稠密图
经常用
o(n^2)
算法流程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int n;      // n表示点数
int g[N][N]; // 邻接矩阵,存储所有边
int dist[N]; // 存储其他点到当前最小生成树的距离
bool st[N]; // 存储每个点是否已经在生成树中


// 如果图不连通,则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
memset(dist, 0x3f, sizeof dist);

int res = 0;
for (int i = 0; i < n; i ++ )
{
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;

if (i && dist[t] == INF) return INF;

if (i) res += dist[t];
st[t] = true;

for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
}

return res;
}


堆优化版prim算法 (不常用)

不经常用
o(mlogn)

克鲁斯卡尔(kruskal)算法 (稀疏图)

o(mlogm)

算法流程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

int n, m; // n是点数,m是边数
int p[N]; // 并查集的父节点数组

struct Edge // 存储边
{
int a, b, w;

bool operator< (const Edge &W)const
{
return w < W.w;
}
}edges[M];

int find(int x) // 并查集核心操作
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}

int kruskal()
{
sort(edges, edges + m);

for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集

int res = 0, cnt = 0;
for (int i = 0; i < m; i ++ )
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w;

a = find(a), b = find(b);
if (a != b) // 如果两个连通块不连通,则将这两个连通块合并
{
p[a] = b;
res += w;
cnt ++ ;
}
}

if (cnt < n - 1) return INF;
return res;
}


单源(起点)最短路

只有一个起点
n m都很大

所有边都是正数

朴素Dijkstra算法

o(n^2) 点数^2
稠密图
邻接矩阵

20220116171410

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int g[N][N];  // 存储每条边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路,如果不存在则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

for (int i = 0; i < n - 1; i ++ )
{
int t = -1; // 在还未确定最短路的点中,寻找距离最小的点
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;

// 用t更新其他点的距离
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);

st[t] = true;
}

if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}



堆优化版Dijkstra算法

o(mlogn) 边数 * log点数
稀疏图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
typedef pair<int, int> PII;

int n; // 点的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储所有点到1号点的距离
bool st[N]; // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离,如果不存在,则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1}); // first存储距离,second存储节点编号

while (heap.size())
{
auto t = heap.top();
heap.pop();

int ver = t.second, distance = t.first;

if (st[ver]) continue;
st[ver] = true;

for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}

if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}


存在负权边

Bellman-Ford

o(nm)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int n, m;       // n表示点数,m表示边数
int dist[N]; // dist[x]存储1到x的最短路距离

struct Edge // 边,a表示出点,b表示入点,w表示边的权重
{
int a, b, w;
}edges[M];

// 求1到n的最短路距离,如果无法从1走到n,则返回-1。
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

// 如果第n次迭代仍然会松弛三角不等式,就说明存在一条长度是n+1的最短路径,由抽屉原理,路径中至少存在两个相同的点,说明图中存在负权回路。
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
/*
if (dist[b] > dist[a] + w)
dist[b] = dist[a] + w;
*/
//松弛操作
dist[b] = min(dist[b],dist[a]+w)
}
}

if (dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];
}



20220124142822

SPFA

一般o(m),最坏o(mn)
没有负环就可以用
99%的题目都可以用
都是正边有时也能用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储每个点到1号点的最短距离
bool st[N]; // 存储每个点是否在队列中

// 求1号点到n号点的最短路距离,如果从1号点无法走到n号点则返回-1
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

queue<int> q;
q.push(1);
st[1] = true;

while (q.size())
{
auto t = q.front();
q.pop();

st[t] = false;

for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j]) // 如果队列中已存在j,则不需要将j重复插入
{
q.push(j);
st[j] = true;
}
}
}
}

if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}


判断是否存在负环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N], cnt[N]; // dist[x]存储1号点到x的最短距离,cnt[x]存储1到x的最短路中经过的点数
bool st[N]; // 存储每个点是否在队列中

// 如果存在负环,则返回true,否则返回false。
bool spfa()
{
// 不需要初始化dist数组
// 原理:如果某条最短路径上有n个点(除了自己),那么加上自己之后一共有n+1个点,由抽屉原理一定有两个点相同,所以存在环。

queue<int> q;
for (int i = 1; i <= n; i ++ )
{
q.push(i);
st[i] = true;
}

while (q.size())
{
auto t = q.front();
q.pop();

st[t] = false;

for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true; // 如果从1号点到x的最短路中包含至少n个点(不包括自己),则说明存在环
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}

return false;
}


多源(起点)汇最短路

起点终点都不确定
n很小,m很大

Floyd算法

o(n^3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

初始化:
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (i == j) d[i][j] = 0;
else d[i][j] = INF;

// 算法结束后,d[a][b]表示a到b的最短距离
void floyd()
{
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}



20220124164427

是一种特殊的图

无向图

特殊的有向图

有向图的存储

邻接矩阵

二维数组
g[a][b] 表示a->b

邻接表(用的最多)

单链表
每一个点都是一个单链表
存储的是每个点可以到达哪些点

对于每一个节点,都开一个单链表(类似拉链法)存储该节点可以访问到的点,存储次序无关紧要。

20220115195751

插入边:

20220115195807

插入操作:

不带权值

1
2
3
4
5
6
7
8
9
10
//邻接表
int h[N], e[M], ne[M], idx;// M = 2 * N

//插入边a ---> b
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}


带权值:

1
2
3
4
5
6
7
int h[N], w[N], e[N], ne[N], idx;

void add(int a, int b, int c) // 添加一条边a->b,边权为c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a]. h[a] = idx ++;
}

1
2
3
4
5
6
7
8
9
10
11
12
// 对于每个点k,开一个单链表,存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

// 添加一条边a->b
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);

遍历方式

深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
bool st[N];//true表示已经用过

int dfs(int u)
{
st[u] = true; // st[u] 表示点u已经被遍历过

//遍历u的邻接点
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];//拿到出边的对应的节点编号
if (!st[j]) dfs(j);//如果没有被访问过,继续递归深搜
}
}

树的重心:

20220115200244

20220115191737

宽度优先搜索

图宽搜的框架和前面BFS的框架基本一模一样,只是将图的结构扩展到宽搜框架里。前面的BFS是根据具体题目来扩展点,图的话采用邻接表存储图,从1号节点编号开始,扩展的是每一个点的临边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1. queue <---- 1号点

2. while(队列不为空)
{

t <---队头
弹出队头

扩展队头元素(扩展t的所有邻接点j)
{
获取邻接点(编号)j
if(j未遍历,符合条件)// 第一次遍历才是最短路径
{
queue <----- j入队// (邻接节点)
更新距离 //d[x] = d[t]++
}
}

}

3. 最后队为空,结束

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size())
{
int t = q.front();
q.pop();

for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true; // 表示点j已经被遍历过
q.push(j);
}
}
}

拓扑排序

有向图
不存在环 即 有向无环图
宽搜

拓扑序列:在一个有向图无环中,对所有的节点进行排序,要求没有一个节点指向它前面的节点。即,所有的边从前指向后!

重要结论性质:一个有向无环图至少存在一个入度为0的节点!

求解步骤:

(1)先统计好图中所有点的入度情况

(2)找到图中入度为0的节点,将它删去,由它发射出来的所有边也要删掉,即它指向的邻接节点度数-1

(3)将删去节点后剩下的图,继续按(2)的规则继续删节点。

按照节点被删除的顺序,依次把这些被删除的节点记录要一个序列里边,当图中所有节点被删除后,那么这个序列就是一个拓扑序列了!

20220115200539

注:当同时出现两个或以上入度为0的节点时,拓扑序列结果不唯一!

20220115200558

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool topsort()
{
1. queue <---- 所有度为0的点

2. while queue不为空
{
t <---- 队头
弹出队头

枚举t所有的出边 t ---> j
{
删掉出边 t ---> j: d[j] --;// 入度-1

if(d[j] == 0)// 当节点j入度为0时,入队
queue <---- j
}
}

如果有n - 1个节点入队的话,说明是拓扑序列返回true,否则不是返回false
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

bool topsort()
{
int hh = 0, tt = -1;

// d[i] 存储点i的入度
for (int i = 1; i <= n; i ++ )
if (!d[i])
q[ ++ tt] = i;

while (hh <= tt)
{
int t = q[hh ++ ];

for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (-- d[j] == 0)
q[ ++ tt] = j;
}
}

// 如果所有点都入队了,说明存在拓扑序列;否则不存在拓扑序列。
return tt == n - 1;
}


DFS深度优先搜索

栈实现
空间o(h)
不具有最短路性质
演示图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Void DFS(deep,...){
if(找到解 || 走不下去了){
......//根据题意添加
return;
}

//for循环遍历每一种情况,例如:每一列都可能出现;1,2,3,4···每一个数字都可能出现
//对这些可能出现的进行for循环遍历
for(扩展方式){
if(扩展方式所能达到的状态合法){
修改操作;//根据题意添加
标记;
DFS(deep+1,...);
//根据题意是否要还原
}
}

}

例题

排列组合

20220115153422

八皇后

n-皇后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>

using namespace std;

const int N = 20;

int n;
char g[N][N];
bool col[N],dg[N],udg[N];//记录是否用过,列,正反对角线

inline void dfs(int u)
{

if(u==n)
{
for(int i=0;i<n;i++) puts(g[i]);
puts("");
return;
}
for(int i=0;i<n;i++)//遍历该层的每一种情况,一共n列 n种情况
if(!col[i] && !dg[u+i] && !udg[n-u+i])
{
g[u][i]='Q';

col[i]=dg[u+i]=udg[n-u+i]=true;
dfs(u+1);
col[i]=dg[u+i]=udg[n-u+i]=false;//恢复现场
g[u][i]='.';
}


}

int main()
{
cin >> n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
g[i][j]='.';
dfs(0);


return 0;
}

BFS深度优先搜索

队列实现
空间o(2^h)
最短路

演示图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void BFS(){
初始化队列Q;
起点S入队;
标记S已经访问;
while(Q非空){
取Q的队首元素U;
U出队列;
if(u==目标状态){
返回结果;
}
for(所有与U相邻的元素){
if(相邻的元素合法 && 未访问){
入队;
标记访问;
}
}
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
typedef pair<int, int> PII;
queue<PII> q;

const int N = 110;
int g[N][N];
int d[N][N]; //存放各个点到起点的距离(最短)

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, m;

int bfs()
{
memset(d, -1, sizeof d);//初始距离全部设置为-1 表示该点未被访问过(记录距离的同时,起到了st数组的作用)
q.push({0, 0});
d[0][0] = 0;

while(q.size())
{
auto t = q.front();
q.pop();

for(int i = 0; i < 4; i ++)
{
int a = t.first + dx[i], b = t.second + dy[i];
if(a < 0 || a >= n || b < 0 || b >= m) continue;//越界
if(g[a][b]) continue;//撞墙
if(d[a][b] != -1) continue;//该点被访问过

q.push({a, b});
d[a][b] = d[t.first][t.second] + 1;//更新距离

}
}

//返回到终点的最短距离
return d[n - 1][m - 1];
}

#include
vector a
vector 变长数组,倍增思想
size()
empty()
clear()
front()/back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算,按字典序

pair<int, int>

first 第一个元素
second 第二个元素
支持比较运算,以first为第一关键字,second第二关键字(字典序)

#include
string 字符串

substr(起始下标, 长度) 返回子串
size()/length() 返回字符串长度
c_str() 返回字符串的首地址
empty()
clear()
to_string(x)

#include
queue 队列

size()
empty()
push() 向队尾插入一个
front() 返回队头
back() 返回队尾
pop() 弹出队头

#include
priority_queue 优先队列(堆)默认大根堆

push() 插入一个元素
top() 返回堆顶
pop() 弹出堆顶

定义成小根堆方式:
priority_queue<int , vector<int>,greater<int>> heap;//创建小根堆
priority_queue<int> heap
heap.push(-x)//创建小根堆

#include
stack 栈

size() 栈的大小/长度
empty() 是否为空
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素

#include
deque 双端队列,队头队尾都可以插入删除

size()
empty()
clear()
front()
back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
很少用,速度太慢了

set,map,multiset,multimap 基于平衡二叉树(红黑树),动态维护有序序列

size()
empty()
clear()
begin()/end() ++ -- 返回前驱后继  O(logn)


set/multiset
    insert() 插入一个数
    find() 查找一个数
    count() 返回某个数的个数
    erase()
        输入是一个数x,删除所有x  O(k+log n)
        输入一个迭代器,删除这个迭代器
    lower_bound()/upper_bound()
        lower_bound(x) 返回大于等于x的最小的数
        upper_bound(x) 返回大于x的最小的数

map/multimap
    insert() 插入的数是一个pair
    erase() 输入的参数是pair或者迭代器
    find()
    []  像数组一样使用 O(logn)
    lower_bound()/upper_bound()

unordered_set,unordered_map,unordered_multiset,unordered_multimap,哈希表

和上面类似,增删改查的时间复杂度是O(1)
不支持lower_bound()/upper_bound() 因为内部是无序的
不支持迭代器的++ --

bitset,压位
用于存储bool量
bitset<10000> S;
~s,&,|,^
>>,<<
==,!=
[]
count() 返回有多少个1

any() 判断是否至少有一个1
none() 判断全为0

set() 把所有位置变为1
set(k,v) 将第K位变成V
reset() 把所有位变为0
flip() 等价于~
flip() 把第K位取反
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
vector<int> a;//定义一个vector
vector<int> a(10);//定义长度为10的vector
vector<int> a(10,3);//定义长度为10的vector,并初始化值为3
a.size();//返回元素个数---所有容器都有
a.empty();//判断是否为空---所有容器都有
a.clear();//清空---队列没有这个函数


a.front();//返回第一个数
a.back();//返回最后一个数
a.push_back();//向最后插入一个数
a.pop_back();//删掉最后一个元素

a.begin()//第一个数
a.end()//最后一个数的后面一个
for(vector<int>::iterator i=a.begin() ; i!=a.end(); i++)
{
cout<< *i <<" ";
}

//支持比较运算





//常用于存不同属性,按照某一种属性进行排序
pair<int, string> p;
pair<int, pair<int, string>> p;//存3个
p.first ,第一个元素
p.second,第二个元素
支持比较运算,以first为第一关键字,second第二关键字
p = make_pair(10,"xiaoming")
p ={20,"xiaohong"}





//----
string a="aaa";
a=a+"bbb";
a+="c";

size()/length()
cout<< a.substr(1,2)<<endl;//从下标1开始返回两个
a.substr(1)//从下标1开始的一个子串

printf("%s\s",a.c_str());//字符串a的起始地址
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#include <set>

#include <map>
using namespace std;

int main()
{

set<int> S;//不允许重复元素
multiset<int> MS;//允许重复元素
return 0;


map<string,int> m;
m["aaa"]=1;
cout<<a["aaa"]<<endl;

}

哈希表

哈希函数,把一个大的范围,映射为一个小的范围
离散化是一种特殊的哈希方式
用于对数据的快速插入和读取

存储结构(处理冲突)

拉链法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int h[N], e[N], ne[N], idx;

// 向哈希表中插入一个数
void insert(int x)
{
int k = (x % N + N) % N;//保证余数是正数
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++ ;
}

// 在哈希表中查询某个数是否存在
bool find(int x)
{
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i])
if (e[i] == x)
return true;

return false;
}


20220113161351
20220113161312

开放寻址法(常用)

开数组时要大2~3倍

1
2
3
4
5
6
7
8
9
10
11
12
13
int h[N];

// 如果x在哈希表中,返回x的下标;如果x不在哈希表中,返回x应该插入的位置
int find(int x)
{
int t = (x % N + N) % N;
while (h[t] != null && h[t] != x)//坑位有人,并且不是x
{
t ++ ;//向后找
if (t == N) t = 0;//到最后,t=0,从头开始循环
}
return t;
}

开放寻址法

字符串哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
核心思想:将字符串看成P进制数,P的经验值是13113331,取这两个值的冲突概率低
小技巧:取模的数用2^64,这样直接用unsigned long long存储,溢出的结果就是取模的结果

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}


20220113172122

完全二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 下标从1开始
// h[N]存储堆中的值, h[1]是堆顶,x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置(下标)
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点,及其映射关系
void heap_swap(int a, int b)
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}

void down(int u)
{
int t = u;
//左儿子小,t等于左儿子
if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
//右儿子小,t等于右儿子
if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
//说明根节点不是最小的
if (u != t)
{
//把根节点和最小的进行交换
heap_swap(u, t);
down(t);
}
}

void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
heap_swap(u, u / 2);
u >>= 1;
}
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);


20220112192917

并查集

将两个集合合并–》例如连通分支合并一个

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

近乎O(1)

简单理解(转载)

为了解释并查集的原理,我将举一个更有爱的例子。 话说江湖上散落着各式各样的大侠,有上千个之多。他们没有什么正当职业,整天背着剑在外面走来走去,碰到和自己不是一路人的,就免不了要打一架。但大侠们有一个优点就是讲义气,绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”,只要是能通过朋友关系串联起来的,不管拐了多少个弯,都认为是自己人。这样一来,江湖上就形成了一个一个的群落,通过两两之间的朋友关系串联起来。而不在同一个群落的人,无论如何都无法通过朋友关系连起来,于是就可以放心往死了打。但是两个原本互不相识的人,如何判断是否属于一个朋友圈呢?

我们可以在每个朋友圈内推举出一个比较有名望的人,作为该圈子的代表人物,这样,每个圈子就可以这样命名“齐达内朋友之队”“罗纳尔多朋友之队”……两人只要互相对一下自己的队长是不是同一个人,就可以确定敌友关系了。

但是还有问题啊,大侠们只知道自己直接的朋友是谁,很多人压根就不认识队长,要判断自己的队长是谁,只能漫无目的的通过朋友的朋友关系问下去:“你是不是队长?你是不是队长?”这样一来,队长面子上挂不住了,而且效率太低,还有可能陷入无限循环中。于是队长下令,重新组队。队内所有人实行分等级制度,形成树状结构,我队长就是根节点,下面分别是二级队员、三级队员。每个人只要记住自己的上级是谁就行了。遇到判断敌友的时候,只要一层层向上问,直到最高层,就可以在短时间内确定队长是谁了。由于我们关心的只是两个人之间是否连通,至于他们是如何连通的,以及每个圈子内部的结构是怎样的,甚至队长是谁,并不重要。所以我们可以放任队长随意重新组队,只要不搞错敌友关系就好了。于是,门派产生了。

20210803124721

下面我们来看并查集的实现。 int pre[1000]; 这个数组,记录了每个大侠的上级是谁。大侠们从1或者0开始编号(依据题意而定),pre[15]=3就表示15号大侠的上级是3号大侠。如果一个人的上级就是他自己,那说明他就是掌门人了,查找到此为止。也有孤家寡人自成一派的,比如欧阳锋,那么他的上级就是他自己。每个人都只认自己的上级。比如胡青牛同学只知道自己的上级是杨左使。张无忌是谁?不认识!要想知道自己的掌门是谁,只能一级级查上去。 find这个函数就是找掌门用的,意义再清楚不过了(路径压缩算法先不论,后面再说)。

1
2
3
4
5
6
7
int find(int x)                    //查找我(x)的掌门
{
int r=x; //委托 r 去找掌门
while (pre[r]!=r) //如果r的上级不是r自己(也就是说找到的大侠他不是掌门 = =)
r=pre[r] ; // r 就接着找他的上级,直到找到掌门为止。
return r; //掌门驾到~~~
}

再来看看路径压缩算法。建立门派的过程是用join函数两个人两个人地连接起来的,谁当谁的手下完全随机。最后的树状结构会变成什么胎唇样,我也完全无法预计,一字长蛇阵也有可能。这样查找的效率就会比较低下。最理想的情况就是所有人的直接上级都是掌门,一共就两级结构,只要找一次就找到掌门了。哪怕不能完全做到,也最好尽量接近。这样就产生了路径压缩算法。 设想这样一个场景:两个互不相识的大侠碰面了,想知道能不能揍。 于是赶紧打电话问自己的上级:“你是不是掌门?” 上级说:“我不是呀,我的上级是谁谁谁,你问问他看看。” 一路问下去,原来两人的最终boss都是东厂曹公公。 “哎呀呀,原来是记己人,西礼西礼,在下三营六组白面葫芦娃!” “幸会幸会,在下九营十八组仙子狗尾巴花!” 两人高高兴兴地手拉手喝酒去了。 “等等等等,两位同学请留步,还有事情没完成呢!”我叫住他俩。 “哦,对了,还要做路径压缩。”两人醒悟。 白面葫芦娃打电话给他的上级六组长:“组长啊,我查过了,其习偶们的掌门是曹公公。不如偶们一起及接拜在曹公公手下吧,省得级别太低,以后查找掌门麻环。” “唔,有道理。” 白面葫芦娃接着打电话给刚才拜访过的三营长……仙子狗尾巴花也做了同样的事情。 这样,查询中所有涉及到的人物都聚集在曹公公的直接领导下。每次查询都做了优化处理,所以整个门派树的层数都会维持在比较低的水平上。路径压缩的代码,看得懂很好,看不懂也没关系,直接抄上用就行了。总之它所实现的功能就是这么个意思。

20210803124845

acwing模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
原模板:

int find (int x)
{
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
可以把y总的模板拆分一下,会方便理解些

int find (int x)
{
if(x != p[x])
{
int t = find(p[x]); //寻找根结点,找到后回溯
p[x] = t; //路径压缩
}
return p[x];
}


p[find(a)]=find(b);//集合合并操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include<iostream>

using namespace std;

const int N=100010;
int p[N];//定义多个集合

int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
/*
经上述可以发现,每个集合中只有祖宗节点的p[x]值等于他自己,即:
p[x]=x;
*/
return p[x];
//找到了便返回祖宗节点的值
}

int main()
{
int n,m;
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=='M') p[find(a)]=find(b);//集合合并操作
else
if(find(a)==find(b))
//如果祖宗节点一样,就输出yes
printf("Yes\n");
else
printf("No\n");
}
return 0;
}

20220112173034

ACWING模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
(1)朴素并查集:

int p[N]; //存储每个点的祖宗节点

// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}

// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;

// 合并a和b所在的两个集合:
p[find(a)] = find(b);


(2)维护size的并查集:

int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义,表示祖宗节点所在集合中的点的数量

// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}

// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
size[i] = 1;
}

// 合并a和b所在的两个集合:
size[find(b)] += size[find(a)];
p[find(a)] = find(b);


(3)维护到祖宗节点距离的并查集:

int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x)
{
int u = find(p[x]);
d[x] += d[p[x]];
p[x] = u;
}
return p[x];
}

// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
d[i] = 0;
}

// 合并a和b所在的两个集合:
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题,初始化find(a)的偏移量



trie树(前缀树)

高效快速的存储和查找字符串集合的数据结构

20220112144921

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int son[N][26], cnt[N], idx;
// 0号点既是根节点,又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';//把字母a-z映射为0-25
if (!son[p][u]) son[p][u] = ++ idx;//不存在子节点
p = son[p][u];
}
cnt[p] ++ ;
}

// 查询字符串出现的次数
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];
}