真----并查集学习笔记（持续更新）

佚名 6年前 (2019-04-09) 随笔 2123人围观抢沙发百度已收录

2019-04-10更新

关于并查集

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

本子上说，并查集“处理的是‘集合’之间的关系，即动态地维护和处理集合元素之间复杂的关系”。

边上图边说

现给出这张图中节点的两两关系，并在给出关系的指令中间插入一些“询问某两个节点是否连通”的指令，要求

随时响应，这样的问题如何解决？

并查集是解决这个问题的一种方法。

上图

假设某一时刻根据给出的关系，节点的连通状态如上图所示，

此时若询问节点9和节点4是否连通，得到的回答应是“是的”。

如果用并查集做这个题，可以将每个已声明关系的节点接入到一颗树中，

都知道一棵树只有一个根节点，那么如果两个节点经声明关系后是连通的，

那么在并查集中，这两个节点的根节点是一个节点，并查集的查询操作，就是

建立在根节点查询的基础上的。

————————————————————————

个人觉得，并查集的路径压缩使得并查集更像并查集，

上图

这是普通并查集的一个集合

这是加入优化代码且优化过一轮后的一个并查集集合

速度上看，例如从五号节点找到零号节点，显然是第二张图显示的这颗树更快一点吧？

根节点是集合的“身份证”，身份证自然还是随身最好，总不能让他人保管，他人又让他人

保管，他人又让他人保管，这样要获得自己的身份证明就会很麻烦，时间上行不通，

联想到并查集，这也许就是路径压缩的意义——去除昂余信息，加快查询速度。

————————————————

1347：【例4-8】格子游戏（好练习题）

http://ybt.ssoier.cn:8088/problem_show.php?pid=1347

这题解析以后再写，先鸽着

1387：搭配购买(buy)

这题等学了背包再做

P1197 [JSOI2008]星球大战

时间限制1 s 内存限制128.00 MB

https://www.luogu.org/fe/problem/P1197

（题解，边做边写）

题目描述

很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治着整个星系。

某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。

但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。

现在，反抗军首领交给你一个任务：给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序，以尽量快的速度求出每一次打击之后反抗军占据的星球的连通块的个数。

（如果两个星球可以通过现存的以太通道直接或间接地连通，则这两个星球在同一个连通块中）。

输入格式

输入文件第一行包含两个整数，N (1 < = N < = 2M) 和 M (1 < = M < = 200,000)，分别表示星球的数目和以太隧道的数目。星球用 0 ~ N-1 的整数编号。

接下来的 M 行，每行包括两个整数 X, Y，其中（ 0 < = X <> Y0<=X<>Y 表示星球 x 和星球 y 之间有 “以太” 隧道，可以直接通讯。

接下来的一行为一个整数 k ，表示将遭受攻击的星球的数目。

接下来的 k 行，每行有一个整数，按照顺序列出了帝国军的攻击目标。

这 k 个数互不相同，且都在 0 到 n−1 的范围内。

输出格式

第一行是开始时星球的连通块个数。接下来的 K 行，每行一个整数，表示经过该次打击后现存星球的连通块个数。

看数据范围，m可以到200000，n可以到400000，k也可以到400000，

首先考虑用并查集求联通快个数，k次销毁，每次都要数n次来求联通块个数，按这道题的

时间限制是会超时的，所以考虑“倒着来”，从最终星球的状态开始，

让时间“倒流”，每次都往集合里添加一个星球，这样，求联通块的复杂度

就降低了，（从重新建立并查集并以O(n)的时间计数到一个if判断联通快数量，还是快了不少的）

代码先鸽着，写完再交

注意，代码放到dev-c++上，再按ctrl+shift+a，可以自动整理代码，如果要读我的代码，请放到ide上按快捷键

先上主函数

int main() {
n=read();
m=read();
for(register int i=0; i<=n-1; ++i) 初始化并查集和链表
　　fa[i]=i,head[i]=-1;

int x,y;

for(register int i=1; i<=m; ++i) { 根据输入建图
x=read();
y=read();
Add(x,y);
Add(y,x);
}

int k=read();
for(register int i=1; i<=k; ++i) { 将发生过的事储存，方便时间倒流
broke[i]=read();
broken[broke[i]]=1;
}
int ans=n-k;
for(register int i=0; i<=n-1; ++i) {
if(broken[i]) continue;
for(register int j=head[i]; j!=-1; j=edge[j].nexty) { 这是将最后一次摧毁后的状态（联通快个数）算出来，方便时间倒流
if(!broken[edge[j].z])
{
if(find(i)!=find(edge[j].z))
{
join(i,edge[j].z);
ans--;
}
}
}
}
answer[k]=ans;记录计算出的状态

for(register int i=k;i>=1;--i) 时间倒流
{
broken[broke[i]]=0;
ans++;
for(register int j=head[broke[i]];j!=-1;j=edge[j].nexty)
if(!broken[edge[j].z])
{
int r1=find(edge[j].z);
int r2=find(broke[i]);
if(r1!=r2)
{
ans--;
join(edge[j].z,broke[i]);
}
}

answer[i-1]=ans;
}

for(int i=0;i<=k;++i)
{
print(answer[i]);
putchar('\n');
}

return 0;
}

下面给出自定义函数、变量名和头文件

#include<cstdio>
#include<iostream>
#include<cstring>

const int maxn=200002;
struct Edge {
int z,nexty;
} edge[maxn*2+3];

int k,n,m,tot,fa[maxn*2],head[maxn*2];

int broke[maxn*2],answer[maxn*2];
bool broken[maxn*2];

inline void Add(int a,int b) {
tot++;
edge[tot].z=b;
edge[tot].nexty=head[a];
head[a]=tot;
}
inline int read() {
char c=getchar();
int x=0,f=1;
while(c<'0'||c>'9') {
if(c=='-') f=-f;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int find(int x) {
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
void join(int a,int b) {
a=find(a);
b=find(b);
fa[b]=fa[a];
}
void print(int x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
}