p1141 01（并查集 + 搜索

**并查集与搜索**

并查集是一种用于解决图论问题的数据结构，特别是在寻找连通分量方面。它通过将相邻的元素合并起来来实现。结合并查集与搜索算法，可以有效地解决许多图论问题。

### 并查集并查集（Union-Find）是一种用于管理一个集合中元素之间关系的数据结构。它可以帮助我们快速找到两个元素是否属于同一集合，或者将两个元素合并到同一集合中。

#### 并查集基本操作1. **Find(x)**：寻找元素x所在的集合。
2. **Union(x, y)**：将元素x和y所在的集合合并。

### 搜索算法搜索算法（Search）用于遍历图中的所有顶点，找到满足某些条件的顶点或边。结合并查集，可以实现更高效的搜索。

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

1. **Start**：从一个起始顶点开始。
2. **Visit**：访问当前顶点。
3. **Explore**：探索当前顶点的邻居。
4. **Backtrack**：回溯到上一个顶点。

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

1. **Start**：从一个起始顶点开始。
2. **Visit**：访问当前顶点。
3. **Enqueue**：将当前顶点的邻居加入队列。
4. **Dequeue**：取出队列中的顶点。

### 并查集与搜索结合通过使用并查集，可以在搜索过程中快速判断两个顶点是否属于同一集合，从而避免重复访问。同时，使用并查集可以将相邻的元素合并起来，使得搜索更加高效。

####代码示例（Python）

class UnionFind:
 def __init__(self, n):
 self.parent = list(range(n))
 self.rank = [0] * n def find(self, x):
 if self.parent[x] != x:
 self.parent[x] = self.find(self.parent[x])
 return self.parent[x]

 def union(self, x, y):
 root_x = self.find(x)
 root_y = self.find(y)

 if root_x != root_y:
 if self.rank[root_x] > self.rank[root_y]:
 self.parent[root_y] = root_x elif self.rank[root_x] < self.rank[root_y]:
 self.parent[root_x] = root_y else:
 self.parent[root_y] = root_x self.rank[root_x] +=1def dfs(graph, start):
 visited = set()
 stack = [start]

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

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

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

 return visited# 示例图graph = {
1: [2,3],
2: [4,5],
3: [6,7],
4: [],
5: [],
6: [],
7: []
}

uf = UnionFind(8)
print(dfs(graph,1)) # {1,2,3,4,5,6,7}
print(bfs(graph,1)) # {1,2,3,4,5,6,7}

uf.union(1,2)
uf.union(2,3)
print(dfs(graph,1)) # {1,2,3,4,5,6,7}