讲义
引例1
•有N个计算机中心，开始时都是独立的。后来不断的架设了M条网线，每条网线把其中的2个计算机中心连接起来。
•直接或间接连接的计算机中心都可以相互通信，组成一个网络。
•问有多少个连通网络？
引例2
•围棋的棋子有黑色和白色两种，相同颜色的棋子如果是上下或左右相邻的，则称这两个棋子是连通的，直接或间接连通的棋子称为一块棋。
•现在，不断给出N个落棋子的信息(颜色、横坐标、纵坐标)，问棋盘上有多少块棋？
建立数学模型
•计算机中心、棋子 --- 点
•网线、相邻 --- 两点关系 --- 边
•网络、块 --- 连通块
查找操作(Find)
•检查：两个点是否在一个连通快
合并操作(Union)
•合并：添加一条连线
方法名称:并查集(Union-Find Set)
•合并 --- Union
•检查 --- Find
•点集 --- Set
“暴力”算法
•一个连通块的点用相同的id表示
•检查：只要看两个点的id是否相同！
•合并1：加边（3,4），两端点在一个连通块，不用处理。
•合并2：加边（5，2），两端点不在一个连通块，怎么办？
“暴力”算法
•合并2：加边（5，2），两端点不在一个连通快
•(1)改id相同 (2)连通块数-1
“暴力”算法的时间复杂度
•点N个，边M个：
•合并的时间复杂度：O( min(N,M)*N )
•查找的时间复杂度：O(1)
新方法
树结构
•Tree:根在上的树
•Father:有向边
特点：
•根“没有”有向边
•其他节点有一条有向边指向“父节点”
统一格式：
• 根的有向边指向自己
•检查操作：
两个点有相同的根就是在一个连通块
•合并操作（6，3）
(这里图片可能有误）
•查：找点x的所在“树”的根函数
从x出发，按照fa[x]向上一直找到根
•并：添加关系(a,b)时合并函数：
查找根的时间复杂度问题
•find_root()函数，坏的情况，向上很多层。
“压缩路径”技术---扁平化。
有压缩路径功能的查找函数
用递归写的函数
或
并查集算法时间复杂度
一次查找根find_root()的平均复杂度：
O(5)
一次合并union(a,b)的平均复杂度：
O(5)
算法的总复杂度：
O(M*5+N)
练习
第1题 网络2 查看测评数据信息
有N个计算机中心(编号为1,2,3,…,N)，开始时都是独立的。后来不断的架设了M条网线，每条网线把其中的2个计算机中心连接起来。直接或间接链接的计算机中心都可以相互通信，组成一个网络。问有多少个网络？
输入格式
第1行：两个整数N、M，N范围[1,100000] ，M范围[1,500000]。
下面M行：每行2个整数，表示网线连接的计算机中心编号。
输出格式
一个整数，表示有多少个不连通的网络。
输入/输出例子1
输入：
5 4
1 5
2 3
2 4
3 4
输出：
2
样例解释
无
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int n, m, u1, v1, ans=0, f[N];
int find(int x)
{
if (f[x]==x) return x; //因为根的根是自己，所以如果x=根[x]，证明找到根
return f[x]=find(f[x]); //压缩路径，找到根后，把x的根=最终联通块的根
}
int main()
{
//网络，边输入边判联通性
scanf("%d%d", &n, &m);
for (int i=1; i<=n; i++) f[i]=i; //刚开始假设根是自己
ans=n; //假设刚开始联通块为n
for (int i=1; i<=m; i++)
{
scanf("%d%d", &u1, &v1);
//等于join函数
int roota=find(u1); //分别找根
int rootb=find(v1);
if (roota!=rootb) //不属于同一个根，不联通
f[roota]=rootb, ans--; //联通块--，但是两块相连
//join结尾
}
printf("%d", ans);
return 0;
}
第2题 围棋1 查看测评数据信息
围棋的棋子有黑色和白色两种，相同颜色的棋子如果是上下或左右相邻的，则称这两个棋子是连通的，直接或间接连通的同色棋子称为一块棋。
现在，给出N个落棋子的信息(颜色、横坐标、纵坐标)，问棋盘上有多少块棋？
输入格式
第一行一个正整数N，范围[1,300]。
下面N行，每行3个正整数c,x,y表示一个棋子的颜色、横坐标、纵坐标。c=1为黑色，c=2为白色；x,y的范围[1,19]
输出格式
一个正整数，表示棋盘上有多少块棋。
输入/输出例子1
输入：
6
1 3 3
2 2 2
1 3 2
2 1 2
1 2 3
2 1 1
输出：
2
样例解释
无
小技巧：x*max（n, m）+y，所得每个数都不会一样（这个公式只会得出一个固定的数），所以可以利用这个来算方格（x,y）坐标转换成一个数的情况，方便找
#include <bits/stdc++.h>
using namespace std;
const int N=22;
int n, c, x, y, f[N*N], mp[N][N], ans=0;
int dx[]={-1, 0, 0, 1}, dy[]={0, -1, 1, 0};
int find_root(int x) //找根节点
{
if (f[x]==x) return x;
return f[x]=find_root(f[x]);
}
void join(int a, int b) //连边
{
int roota=find_root(a);
int rootb=find_root(b);
if (roota!=rootb)
{
f[rootb]=roota;
ans--;
}
}
int main()
{
//围棋，把棋子向四边扩散，边输入边扩散，看看连不连通即可（联通就ans--，并连边）
scanf("%d", &n);
for (int i=0; i<=19*19; i++) f[i]=i; //刚开始假设根是自己
ans=n; //刚开始假设全部联通
for (int i=1; i<=n; i++)
{
scanf("%d%d%d", &c, &x, &y);
mp[x][y]=c;
for (int j=0; j<4; j++)
{
int nx=x+dx[j], ny=y+dy[j];
if (nx>=1 && nx<=19 && ny>=1 && ny<=19)
if (mp[nx][ny]==c) //颜色相同
join(x*19+y, nx*19+ny); //小技巧，连边
}
}
printf("%d", ans);
return 0;
}
标签：连通,入门,int,复杂度,查集,---,棋子,L2,find From： https://www.cnblogs.com/didiao233/p/18000532