无向图的连通性判别【并查集】记录使用了哪些节点

# 1. 简介

## 1.1 介绍无向图的基本概念和连通性
在图论中，无向图是由一组顶点和一组边组成的图，其中边没有方向。无向图中的顶点通过边连接在一起，形成一个网络结构。图中的连通性指的是图中任意两个顶点之间是否存在路径相连，如果存在，则称这两个顶点是连通的。

## 1.2 简要概述并查集的原理及其在图论中的应用
并查集（Disjoint Set）是一种数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。在图论中，并查集常用于判断图中的连通性，特别是在处理无向图的连通性问题中应用广泛。

# 2. 并查集数据结构介绍

### 2.1 并查集基本操作：合并（Union）与查找（Find）

在并查集数据结构中，通常包含两个基本操作：合并（Union）和查找（Find）。合并操作用于将两个集合合并为一个集合，而查找操作用于确定某个元素属于哪个集合。

### 2.2 并查集路径压缩和按秩合并优化

为了提高并查集的效率，在实际应用中经常会采用路径压缩和按秩合并这两种优化策略。路径压缩可以减小树的高度，使得查找操作更加高效，而按秩合并则可以保持树的平衡，避免出现退化情况，进一步提高了效率。

# 3. 判断无向图的连通性

3.1 使用并查集进行无向图连通性的判断

在图论中，判断无向图的连通性是一个常见且重要的问题。而并查集（Disjoint Set）数据结构正是解决这类问题的利器之一。通过并查集，我们可以判断图中任意两个节点是否连通，从而判断整个图的连通性。

3.2 详细说明如何利用并查集处理无向图中的连通性问题

首先，我们需要初始化一个并查集，将图中的每个节点视为一个单独的集合。然后，依次遍历图中的每条边，对于每条边的两个节点，我们可以通过并查集的“查找”操作（Find）找到它们所在的集合，并判断它们是否属于同一个集合。如果不属于同一个集合，则可以通过“合并”操作（Union）将它们合并成一个集合。

通过不断遍历图中的边并执行合并操作，最终可以判断整个无向图的连通性。如果最终所有节点都属于同一个集合，则图是连通的；反之，图是不连通的。

使用并查集进行无向图的连通性判断具有高效性和简洁性，尤其适用于大规模图的连通性判断和处理。

# 4. 记录并查集中每个连通分量的节点

在使用并查集处理无向图的连通性时，有时需要记录每个连通分量中的具体节点信息。这在某些场景下非常有用，比如在社交网络中查找朋友的朋友，或者在网络连通性问题中查找特定节点所在的连通分量等。

为了实现这一功能，我们可以设计一个数据结构，来记录并查集中每个连通分量的节点。具体实现方式如下：

### 4.1 设计并实现记录节点的数据结构

我们可以定义一个HashMap，其中Key表示连通分量的代表节点（也可以是根节点），Value则是一个列表，用来存储该连通分量中的所有节点。在合并两个连通分量时，我们只需要更新其中一个代表节点对应的列表，将另一个列