流通问题：判断图的连通性与连通图的性质

# 2.1 深度优先搜索（DFS）

深度优先搜索（DFS）是一种图的连通性判定算法，它通过递归的方式沿着图的深度进行搜索。DFS算法的工作原理如下：

1. 从图中选择一个起始顶点，将其标记为已访问。
2. 对于当前顶点的每个未访问的邻接顶点，重复步骤1和步骤2。
3. 当当前顶点的所有邻接顶点都被访问后，回溯到上一个已访问的顶点。
4. 重复步骤1到步骤3，直到所有顶点都被访问。

DFS算法可以通过递归或栈的方式实现。递归实现如下：

def dfs(graph, start):
    visited.add(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor)

# 2. 图的连通性判定算法

### 2.1 深度优先搜索（DFS）

#### 2.1.1 DFS算法原理

深度优先搜索（DFS）是一种图的遍历算法，它以深度优先的方式遍历图中的节点。具体来说，DFS算法从一个起始节点开始，沿着一条路径一直向下遍历，直到无法继续遍历为止，然后回溯到上一个未访问的节点，继续向下遍历。

DFS算法的递归实现如下：

def dfs(graph, start):
    visited.add(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor)

#### 2.1.2 DFS算法实现

DFS算法的实现需要使用一个栈来存储待访问的节点。算法从起始节点开始，将起始节点压入栈中。然后，循环执行以下步骤：

1. 从栈中弹出栈顶元素。
2. 将弹出元素标记为已访问。
3. 遍历弹出元素的所有未访问的邻接节点。
4. 将未访问的邻接节点压入栈中。

重复执行以上步骤，直到栈为空。

def dfs_iterative(graph, start):
    stack = [start]
    visited = set()

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)

### 2.2 广度优先搜索（BFS）

#### 2.2.1 BFS算法原理

广度优先搜索（BFS）是一种图的遍历算法，它以广度优先的方式遍历图中的节点。具体来说，BFS算法从一个起始节点开始，先访问起始节点的所有邻接节点，然后再访问邻接节点的邻接节点，以此类推。

BFS算法的递归实现如下：

def bfs(graph, start):
    queue = [start]
    visited = set()

    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)

#### 2.2.2 BFS算法实现

BFS算法的实现需要使用一个队列来存储待访问的节点。算法从起始节点开始，将起始节点加入队列。然后，循环执行以下步骤：

1. 从队列中取出队首元素。
2. 将队首元素标记为已访问。
3. 遍历队首元素的所有未访问的邻接节点。
4. 将未访问的邻接节点加入队列。

重复执行以上步骤，直到队列为空。

def bfs_iterative(graph, start):
    queue = [start]
    visited = set()

    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)

### 2.3 并查集

#### 2.3.1 并查集数据结构

并查集是一种数据结构，用于维护一组不相交的集合。并查集由两个数组组成：

* parent数组：存储每个元素的父元素。
* rank数组：存储每个集合的秩（集合中元素的个数）。

#### 2.3.2 并查集算法实现

并查集算法主要包括以下两个操作：

* find：查找一个元素所属的集合。
* union：合并两个集合。

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [1 for i in range(n)]

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        ret