最近遇到一道无向图的连通性相关的问题。一般解决图相关的问题，最直接的思路就是利用dfs暴力搜索，因为图可以看成是一种特殊的树。但是在查看题解的时候，发现了另一种巧妙的解法。正是利用上一篇所讲到的并查集来优化暴力的dfs算法。下面看具体题目。
问题描述
小明的实验室有N台电脑，编号1~N。原本这N台电脑之间有N-1条数据链接相连，恰好构成一个树形网络。在树形网络上，任意两台电脑之间有唯一的路径相连。
不过在最近一次维护网络时，管理员误操作使得某两台电脑之间增加了一条数据链接，于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径，使得这些电脑上的数据传输出现了BUG。
为了恢复正常传输。小明需要找到所有在环路上的电脑，你能帮助他吗？
输入格式
第一行包含一个整数N。
以下N行每行两个整数a和b，表示a和b之间有一条数据链接相连。
对于30%的数据，1 <= N <= 1000
对于100%的数据, 1 <= N <= 100000， 1 <= a, b <= N
输入保证合法。
输出格式
按从小到大的顺序输出在环路上的电脑的编号，中间由一个空格分隔。
样例输入
5
1 2
3 1
2 4
2 5
5 3
样例输出
1 2 3 5思路
并查集的原理很简单，具体可以看上一篇文章，这里就不再赘述了。我们重点分析为什么并查集可以解决这个问题。
当并查集录入图的每一条边的时候，都会将这个边的两个节点的根更新一次；又由于这是一张无向连通图，因此所有节点之间都是相互连同的，即最后的根只会有一个值。当新加入的一条边的两个节点的根值相等的时候，就说明这两个节点都曾经作为某条边的端点加入过并查集里了。即 即使不加入这条边，这两个节点之间仍然是连同的。此时再加入一条边，就说明有两条路径可以从a点到b点，即出现了环。下面给出具体的代码。
代码实现
maxn = 100000+5
par = [0]*maxn # 并查集
vis = [0]*maxn # 记录是否遍历过
ret = [0]*maxn # 结果集
edge = [[] for _ in range(maxn)] # 存储每个节点相连的边
res = ''
def find_root(v):
if par[v] != v:
par[v] = find_root(par[v])
return par[v]
def dfs(u, idx, f): # u:当前节点 idx: 结果计数 f:终点
global ret, res
ret[idx] = u # 当前节点加入结果集
if u == f: # 当前节点就是终点 环遍历完成 输出答案
ret = ret[:idx+1]
ret.sort()
for i in range(idx+1):
res = res + str(ret[i]) + (' ' if i!=idx else '\n')
return
vis[u] = 1 # 还没到重点 标记当前节点
for i in range(len(edge[u])): # 遍历当前节点的所有边
v = edge[u][i]
if not vis[v]: # 这条边没有遍历过
dfs(v, idx+1, f)
vis[u] = 0 # 回溯
if __name__ == "__main__":
n = int(input())
for i in range(1, n+1):
par[i] = i
for i in range(n):
tmp = input().split()
u, v = int(tmp[0]), int(tmp[1])
root_u = find_root(u) # 并查集 搜索根
root_v = find_root(v)
if root_u == root_v: # 两节点根相同
s = u # 搜索起点
f = v # 搜索终点
else: # 不相同 进行合并操作
par[root_u] = root_v
edge[u].append(v)
edge[v].append(u)
dfs(s, 0, f)
print(res)小结
通过这道题，让我对并查集的理解又加深了一个层次，并且让我对图的连通性有了新的理解。因此我很好奇并查集到底还有哪些常见的用处。
经过一番资料查找，总结如下：
基本作用 多个不相交集合
无向图的连通性（两点之间是否连通）
判断无向图中的环
最小生成树的Kruskal 算法
