oj并查集判断图中的环

### 使用并查集算法检测图中是否存在环

#### 并查集简介
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。基本操作包括`union`(合并) 和 `find`(查找)，这些操作能够高效地管理动态连通性问题。

#### 实现思路
当尝试构建一棵生成树时，每加入一条新边 `(u, v)` ，先检查这两个顶点是否已经在同一个集合内。如果是，则意味着形成了一个新的回路；如果不是，则将两个顶点所在的集合合并成一个更大的集合[^2]。

#### 示例代码
下面是一个简单的 Python 函数，它接收一个由多个元组组成的列表作为输入参数，其中每个元祖代表了一条连接两个节点之间的无向边，并返回布尔值指示该图是否有环：

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size
    
    def find(self, p):
        if self.parent[p] != p:
            self.parent[p] = self.find(self.parent[p])  # Path compression
        return self.parent[p]

    def union(self, p, q):
        rootP = self.find(p)
        rootQ = self.find(q)

        if rootP == rootQ:
            return False
        
        if self.rank[rootP] > self.rank[rootQ]:
            self.parent[rootQ] = rootP
        elif self.rank[rootP] < self.rank[rootQ]:
            self.parent[rootP] = rootQ
        else:
            self.parent[rootQ] = rootP
            self.rank[rootP] += 1
            
        return True


def has_cycle(edges, n_nodes):
    uf = UnionFind(n_nodes)
    
    for u, v in edges:
        if not uf.union(u - 1, v - 1):  # Adjusting index from 1-based to 0-based
            return True
                
    return False

此函数首先初始化了一个大小为给定节点数量的并查集实例。接着迭代遍历所有的边，在每次调用`uf.union()`之前都会自动完成路径压缩和按秩合并的操作以保持较低的时间复杂度。一旦发现某次联合失败（即两点已经属于同一集合），就立即返回True表明存在至少一个环；否则最终返回False表示不存在任何环。