一、连通图
1．顶点间的连通性
在无向图G中，若从顶点vi到顶点vj有路径(当然从vj到vi也一定有路径)，则称vi和vj是连通的。
对于给定的顶点 p，顶点 q 与顶点 r，连通性具有以下特性：
• 自反性：p 与 p 自身是连通的；
• 对称性：如果 p 与 q 是连通的，那么 q 与 p 也是连通的；
• 传递性：如果 p 与 q 是连通的，q 与 r 是连通的，那么 p 与 r 也是连通的。
2．连通图
若V(G)中任意两个不同的顶点vi和vj都连通(即有路径)，则称G为连通图(Con-nected Graph)。
【例】图G2，和G3是连通图。
3．连通分量
无向图G的极大连通子图称为G的最强连通分量(Connected Component)。
注意：
① 任何连通图的连通分量只有一个，即是其自身
② 非连通的无向图有多个连通分量。
【例】下图中的G4是非连通图，它有两个连通分量H1和H2。
4. 强连通图
有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。
5. 强连通分量
有向图的极大强连通子图称为G的强连通分量。
注意：
① 强连通图只有一个强连通分量，即是其自身。
② 非强连通的有向图有多个强连分量。
【例】下图中的G1不是强连通图，因为v3到v2没有路径，但它有两个强连通分量，如右图所示。
6. 网络(Network)
若将图的每条边都赋上一个权，则称这种带权图为网络。
注意：
权是表示两个顶点之间的距离、耗费等具有某种意义的数。
【例】下图就是一个网络的例子。
二、并查集（Union-find 或 Disjoint-set）
1. 用途背景
首先在地图上给你若干个城镇，这些城镇都可以看作点，然后告诉你哪些对城镇之间是有道路直接相连的。最后要解决的是整幅图的连通性问题。
比如随意给你两个点，让你判断它们是否连通，或者问你整幅图一共有几个连通分支，也就是被分成了几个互相独立的块。
像畅通工程这题，问还需要修几条路，实质就是求有几个连通分支。
如果是1个连通分支，说明整幅图上的点都连起来了，不用再修路了；如果是2个连通分支，则只要再修1条路，从两个分支中各选一个点，把它们连起来，那么所有的点都是连起来的了；如果是3个连通分支，则只要再修两条路……
2. 并查集构成
一个整数型的数组pre[]：
数组pre[]记录了每个点的前导点是什么。
数组下标是当前点的号码，值是前导点的号码，如果值和下标一样代表自己是根。
int pre[1000]; 查找函数find
查找是找根用的，直到找到值和下标一样的根位置
//查找根节点
int find(int x)
{
int r=x;
//返回根节点 r
while ( pre[r ] != r )
r=pre[r ];
int i=x , j ;
//路径压缩
while( i != r )
{
j = pre[ i ]; // 在改变上级之前用临时变量 j 记录下他的值
pre[ i ]= r ; //把上级改为根节点
i=j;
}
return r ;
} 合并函数join
//判断x y是否连通，
//如果已经连通，就不用管了
//如果不连通，就把它们所在的连通分支合并起,
void join(int x,int y)
{
int fx=find(x),fy=find(y);
if(fx!=fy)
pre[fx ]=fy;
}