## 并查集

不相交集合

基本原理

将编号为1...N 的N个对象划分为不相交集合，再每个集合中，选择其中某个元素代表所在集合。

常见两种操作：

合并两个集合

查找某元素属于哪个集合

再某个城市里住着n个人，现在给定n个人的m条信心，即某两个人认识，假设所有认识的人一定属于一个单位，请计算该城市有最多多少单位

用编号最小的元素标记所在集合；

定义一个数组set[1...n],其中set[i]表示元素i所在集合

| i      | 1    | 2    | 3    | 4    |
| ------ | ---- | ---- | ---- | ---- |
| set[i] | 1    | 2    | 1    | 4    |

{1，3，7}:1

{2，5，9}:2

相当告诉是哪个集合的

合并操作

合并以后最小的元素作为集合

把更大的（set[k]==j)合并到set[k]=i

```
find(x)
{
return set[x];
}

Merge(a,b)
{
/*对于最大/最小的合并，所以我觉得应该先
    // 找到a所在集合的代表元素
    rep_a = set[a];
    // 找到b所在集合的代表元素  
    rep_b = set[b];
    
    // 如果已经在同一个集合，不需要合并
    if (rep_a == rep_b)
        return;
        */
i=min(a,b);
j=max(a,b);
for (k=1;k<=N;k++)
{
if (set[k]==j)
 set[k]=i;

}
}
```

合并：效率分析O(n)

树结构如何？

每一个集合用一棵“有根树”表示

定义数组 set[1..n]

set[i]=i,则i表示本集合，并是集合对应树的根

set[i]=j,j<>i,则j是i的父节点

1<-5

2<-4<-7、10

4是7和10

3<-6 、8、9

可能只是父节点而不是根

那怎么判断一个元素属于哪个集合？

```
find2(x)
{
r=x;
while (set[r]!=r)
r=set[r];
retrun r;
}
最坏情况是O(N)
一般情况？
merge2(a,b)
{
set[a]=b;
}
```

时间复杂度为O（1）

避免最坏情况：O(n)

方法：将深度小的树合并到深度大的树

假设两棵树的深度分别为h1和h2

则合并后的树的高度：

max(h1,h2),if h1<>h2

h1+1, u]if h1==h2

包含k个节点的根的最大高度不超过$$\lfloor \lg _k \rfloor $$

```
merge3(a,b)
{
if (height(a)==height(b))
{
height(a)=height(a)+1;
set[b]=a;
}
else if (height(a)<height(b))
	set[a]=b;
else 
set[b]=a;
}
```

带路径压缩的查找操作

```
find2(x)
{}//常规查找操作
merge2(a,b)
{set[a]=b;}
find3(x)
{
if (set[x]!=x)
set[x]=find3(set[x])
}
return set[x];
}
带路径压缩的查找函数
```

记忆化dfs

dfs深搜+递归

不仅找到还修改了父节点的值

越查找越扁平，适合查找次数较多的情况

**后续查找时间复杂度**  O树高 (普通查找)->**O1**或接近常数

![image-20260302161741384](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20260302161741384.png)





[Problem - 1232](https://acm.hdu.edu.cn/showproblem.php?pid=1232)

省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？

测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说

3 3

1 2

1 2

2 1
这种输入也是合法的
当N为0时，输入结束，该用例不被处理。

和集合的数量-1

怎么转换成集合？

```
#include "stdio.h" 
int bin[1002]:
int findx(int x){
int r=x;
while(bin[r] !=r)
	r=bin[r];
		return r;
		}
void merge(int x,int y)
{
int fx,fy;
fx = findx(x):fy = findx(y):if(fx != fy)bin[fx] = fy:
int main()
{ int n,m,i,x,y.count;
while(scanf("%d",&n),n)
{ for(i=l:i<=n:i++)
	bin[i]=i:scanf("%d",&m);
	while(m--)
	{ scanf("%d %d",&x,&y);merge(x.y);
}
for(count=0,i=l:i<=n:i++)
if(bin[i] == i)
count ++;printf("%d\n",count-l):
}
return O:
```

[Problem - 1272](https://acm.hdu.edu.cn/showproblem.php?pid=1272)

但是她设计迷宫的思路不一样，首先她认为所有的通道都应该是双向连通的，就是说如果有一个通道连通了房间A和B，那么既可以通过它从房间A走到房间B，也可以通过它从房间B走到房间A，为了提高难度，小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，前两个是符合条件的，但是最后一个却有两种方法从5到达8。

输入包含多组数据，每组数据是一个以0 0结尾的整数对列表，表示了一条通道连接的两个房间的编号。房间的编号至少为1，且不超过100000。每两组数据之间有一个空行。

并查集的应用：图中有没有环

一条边的两个节点老大是同一个人，说明就成环了（已经相连）

- 如果两个节点已经连通（在同一集合），它们之间已经存在一条路径
- 再添加一条直接连接这两个节点的边，就会形成环



最小生成树

Prim算法

Kruskal算法

理论基础：MST性质：至少存在一棵最小生成树，包含这条最短的边。

先假设所有的最小生成树都不包含最短的这条边，

任选一个生成树，把e加进去，就成了环

把e保留，f去掉，得到一个新的最小生成树

小于等于原来的最小生成树

按权重排序嘛，然后不连通就连接

设Fx是x老大，Fy是y老大，如果Fx不等于Fy，就合并

如果是一样的，就跳过

1. 把原始图的N个节点看成N个独立子图
2. 每次选取当前最短的边前提是？（看两端是否属于不同的子图；若是，加入，否则，放弃直到有N-1条边)





## 二分匹配

### 二分图

引入：

婚配问题：

染色的方法，任选一个点，设为白色，那么连着的一定是黑色的

定义：如果一个图的顶点可以分为两个集合X和Y，图的所有边一定是一个顶点属于集合X，另一个顶点属于集合Y，则称该图为“二分图”或“二部图“(Bipartite Graph)

特点：

DFS实现

**最大匹配**

已有一个二分图，选一些 **互不共享端点的边**，数量最多。要求X和Y一对一匹配



```mermaid
graph LR

subgraph B["女"]
    B1(("女1"))
    B2(("女2"))
    B3(("女3"))
end

subgraph A["男"]
    A1(("男1"))
    A2(("男2"))
end

A1 --- B1
A1 --- B2
A2 --- B3
```

匈牙利算法

二分图的应用中，求最大匹配为题。很多的问题都可以转化为匹配问题来解决。

LCY算法入门——二分图匹配问题

左到右是匹配，右到左是解除

一种是直接匹配成功，一种是间接匹配，否则并没有增加匹配数

本质就是N趟的DFS，如果成功了

复杂度为O(V)

**二分图最小顶点覆盖**

用最小的点覆盖所有的边

每条边至少有一个端点被选中

边依附于点，只要一条边的一个点不在，那么这条边不在；

删除点使得所有边消失等同于用最小顶点覆盖右边

最小顶点覆盖等同的最大匹配集

删除一个点，就相当于去除了所有的边;你匹配了一个点，那么其余的边都无效了。所以最大匹配就相当于顶点覆盖。

见Konig定理的证明

![image-20260309225725899](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20260309225725899.png)

对于一般图来说，最小顶点覆盖 ≥ 最大匹配

任务安排

有两台机器A和B以及N个需要运行的任务。

每台机器有多种不同的模式，而每个任务都恰好在一台机器上运行。

如果它在机器A上运行，则机器A需要设置为模式ai,

如果它在机器B上运行，则机器B需要设置为模式bj。

每台机器上的任务可以按照任意顺序执行，但是每台机器每转换一次模式需要重启一次。

请合理为每个任务安排一台机器并合理安排顺序，使
得机器重启次数尽量少

机器a的模式 机器b的模式 零件数

5 5 10

序号 a的模式 b的模式

0 1 1

1 1 2

2 1 3

3 1 4

4 2 1

5 2 2 

6 2 3

7 2 4

8 3 3

9 4 3

0

网络流问题最核心的就是建图了

把机器a、b的五种模式作为顶点，任务作为边

一开始都在a0，b0状态

分趟dfs,dfs返回True配对成功

本质最小顶点覆盖问题

```
//二分匹配匈牙利算法的DFS实现
//邻接矩阵形式
//uN是匹配左边的顶点数
//vN是匹配右边的顶点数
//k是任务数
//优点:适用于稠密图
//优点:实现简洁易于理解
//时问复杂度:0(VE)
//顶点编号从0开始的
//调用:res=hungary();
//输出最大匹配数
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 510;
int uN,vN://u,v的数目
int g[MAXN][MAXN]://邻接矩阵
int linker[MAXN]://存右点对象对应的左对象的值
bool	used[MAXN];//右点访问否
bool dfs(int u)
{
for(int v=0;v<vN;v++)//遍历右边
if(g[u][v] && !used[v])//这一趟有边并且v没有其他边相连，即直接连接，不管前面有没有
{
	used[v] = true;//右边使用过了，不管前面有没有使用过
·	if(linker[v]=-1||dfs (linker[v]))//如果右边没有与左边相连的，那么一定为-1；否则说明右边与左边相连，dfs右边对应左边的，先断开，这一趟左边的重新找，返回True也行
	{	linker[v] = u;//linker v不会被重置，是每个左边
		return true;
	}	
}
return false://这一句容易忘记。如果遍历了左边的都没有True，那么False；原来的关系可能会变，但不会影响最终false
}
int hungary()
{int res = 0;
memset(linker,-1,sizeof(linker));//全为-1说明还没有与左边相连
for(int u = 0;u < uN;u++)//遍历所有a的模式
{memset (used,false,sizeof (used));//每一趟一开始都要清空used数组，相当于右边都没有使用过
if(dfs(u))res++;
}
return res;
}
int main()
{int k;
while(scanf ("%d",&uN)==1 && uN)
{scanf ("%d%d",&vN,&k);
memset(g,0,sizeof (g));//初始化
int id,u,v;
while(k--)
{
scanf ("%d%d%d",&id,&u,&v);
if (u != 0 &&v != 0)//一开始在0状态，因此不需要转换
g[u][v]=1;
}
printf ("%d\n",hungary());
}
return 0;
}
```

邻接矩阵更适合稀疏图

DAG**有向无环图（DAG）的最小路径覆盖问题**

用最少的（不相交）路径覆盖所有的点

路径覆盖覆盖的是点

顶点覆盖覆盖的是边

空袭

有一个城镇，它的所有街道都是单行的，并且每条街道都是和两个路口相连。同时已知街道不会形成回路。你的任务是编写程序求最小数量的伞兵，这些伞兵可以访问(visit)所有的路口。对于伞兵的起始降落点不做限制。



Input:

4 // 顶点

3//边 

3 4

1 3

 2 3

output:2

为什么空袭中可以将其转换成二分图？

1-3无论是1-3还是3-1，有一条路就凑成一对

这种DAG图呢，既可能是是出发点，也可能是终点

```mermaid
graph LR
 	A((1)) -->C((3))
 	B((2)) -->C
 	C-->D((4))
```



```mermaid
graph LR

 subgraph B
 	
 	B1((1'))
 	B2((2'))
 	B3((3'))
 	B4((4'))
 end
  subgraph A	
	
 		A1((1))
 		A2((2))
 		A3((3))
 		A4((4))
 end
 A1 -->B3
 A2 -->B3
 A3 -->B4
 
```

最大匹配数只有2

每多一个匹配，就少一个伞兵

伞兵数：节点数n-最大匹配数m



**二分图的最大独立集**

最多选几个点

任何两个点之间都没有边

最小顶点覆盖就覆盖了所有的边，也就是说其它的点就是相互独立的

节点数-最大匹配数