第六周0125

一.连通性与无向图
连通性：
在图论中，连通性是指图中顶点之间的可达性。对于一个无向图，如果从任意一个顶点都可以通过路径到达其他任意顶点，那么这个图被称为连通图（Connected Graph）。如果图中存在某些顶点无法通过路径到达其他顶点，则称该图是非连通的。
连通分量：
非连通图可以被划分为若干个极大连通子图，每个子图内部是连通的，但不同子图之间没有边相连。这些子图称为连通分量。
无向图：
无向图是一种图结构，其中的边没有方向。每条边连接两个顶点，但不区分起点和终点。无向图的主要特点包括：
边的表示：边用一对顶点表示，例如 (u,v)，表示顶点 u 和顶点 v 之间有一条边。
对称性：如果 (u,v) 是一条边，那么 (v,u) 也是一条边。
无向图的性质：
度数：一个顶点的度数是与它相连的边的数量。
连通性：无向图可以是连通的或非连通的。
路径和环：路径是顶点序列，其中每对相邻顶点之间有一条边；环是一个起点和终点相同的路径。
连通性与无向图的关系
在无向图中，连通性是一个重要的性质，用于描述图的结构。通过分析连通性，可以解决许多实际问题，例如：
网络设计：确保网络中的每个节点都能相互通信。
社交网络分析：研究用户之间的连接关系。
路径规划：在地图上找到从一个点到另一个点的路径。
示例
假设有一个无向图，包含 5 个顶点和 4 条边：
边：(1,2)，(2,3)，(4,5)
这个图是非连通的，因为它可以被划分为两个连通分量：
连通分量 1：包含顶点 1、2 和 3。
连通分量 2：包含顶点 4 和 5。
如果要使这个图连通，可以添加一条边 (3,4)，这样所有顶点都可以通过路径相互到达。
总结
连通性是图论中的一个重要概念，用于描述图中顶点之间的可达性。无向图是一种图结构，其中的边没有方向。通过分析无向图的连通性，可以解决许多实际问题，例如网络设计和路径规划。
二.并查集路径压缩

int find(int i){
	if(fa[i]==i)return i;
	else return find(fa[i]);
}

路径压缩

int find (int i){
	if(fa[i]==i)return i;
	else {
		fa[i]=find(fa[i]);
		return fa[i];
		}