无向图的连通性判别【并查集】检查是否有环：判断输入边的两个点是否已经使用过

# 1. 简介

无向图是图论中一种基本的图，它由顶点集合和边集合组成，其中的边没有方向。并查集（Union Find）是一种用于处理集合的数据结构，主要支持两种操作：查找（Find）和合并（Union）。本文将介绍如何利用并查集来判断无向图的连通性，以及检查无向图中是否存在环。接下来，我们将对本文内容进行概述。

# 2. 并查集的基本原理

并查集（Union Find）是一种常见的数据结构，用于处理集合的合并及查找问题。在图论中，利用并查集可以方便地进行连通性判别、环检测等操作。本章将介绍并查集的基本原理，包括数据结构、操作方法以及优化技巧。

# 3. 无向图的表示

在进行无向图的连通性判别之前，我们首先需要选择合适的方式来表示无向图。常见的无向图表示方式包括邻接矩阵和邻接表两种形式，它们各有优劣，可以根据具体需求选择合适的表示方式。

#### 3.1 邻接矩阵

邻接矩阵是通过一个二维数组来表示图的连接关系，其中`matrix[i][j]`的值表示顶点`i`到顶点`j`是否有边相连。对于无向图，邻接矩阵是对称的，即`matrix[i][j] == matrix[j][i]`。

#### 3.2 邻接表

邻接表是通过一个数组加上链表或者数组的方式来表示图中每个顶点相邻的顶点集合。对于无向图，邻接表中的每个顶点的相邻顶点集合是无序的，但是所有的边都会被记录两次。

#### 3.3 本文使用的图表示方式选择

在本文中，我们将选择邻接表的方式来表示无向图。邻接表相比邻接矩阵更加节省空间，并且在处理稀疏图时有着更好的性能表现。接下来，我们将基于邻接表的表示方式来进行无向图的连通性判别。

# 4. 判别无向图的连通性

在本章节中，我们将介绍如何利用并查集来判断无向图的连通性。通过并查集的操作，我们可以有效地检查图中的各个节点是否连通，并进一步判断整个图是否是连通的。

#### 4.1 如何利用并查集判断图的连通性

在一个无向图中，如果图中的所有节点都可以相互连通，则称该图是连通的。为了判断图的连通性，我们可以使用并查集来实现。

#### 4.2 并查集的应用实例：判断无向图是否连通

下面我们通过一个具体的例子来演示如何利用并查集来判断无向图是否连通。

# Python示例代码

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.pa