本次题目来自于卡码网

并查集理论基础

并查集可以解决什么问题呢？并查集常用来解决连通性问题。

并查集主要有两个功能：

• 将两个元素添加到一个集合中。
• 判断两个元素在不在同一个集合

代码模板

int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}
// 并查集里寻根的过程
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

通过模板，我们可以知道，并查集主要有三个功能。

• 寻找根节点，函数：find(int u)，也就是判断这个节点的祖先节点是哪个
• 将两个节点接入到同一个集合，函数：join(int u, int v)，将两个节点连在同一个根节点上
• 判断两个节点是否在同一个集合，函数：isSame(int u, int v)，就是判断两个节点是不是同一个根节点

复杂度分析

• 空间复杂度： O(n)
• 时间复杂度：路径压缩后的并查集时间复杂度在O(logn)与O(1)之间，且随着查询或者合并操作的增加，时间复杂度会越来越趋于O(1)。

107. 寻找存在的路径

无向图，判断 一个顶点到另一个顶点有没有有效路径其实就是看这两个顶点是否在同一个集合里。

class UnionFind:
    def __init__(self, n):
        self.n = n  # 节点数量
        self.father = [0] * (n + 1)  # 按照节点大小定义数组大小

        # 并查集初始化
        for i in range(1, n+1):
            self.father[i] = i

    # 并查集里寻根的过程
    def find(self, u):
        if u == self.father[u]:
            return u
        else:
            self.father[u] = self.find(self.father[u])
            return self.father[u]

    # 判断 u 和 v是否找到同一个根
    def isSame(self, u, v):
        u = self.find(u)
        v = self.find(v)
        return u == v

    # 将v->u 这条边加入并查集
    def join(self, u, v):
        u = self.find(u)  # 寻找u的根
        v = self.find(v)  # 寻找v的根
        if u == v:
            return  # 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
        self.father[v] = u


if __name__ == '__main__':
    n, m = map(int, input().strip().split())
    UnionFind = UnionFind(n)
    for _ in range(m):
        s, t = map(int, input().strip().split())
        UnionFind.join(s, t)
    source, destination = map(int, input().strip().split())
    if UnionFind.isSame(source, destination):
        print(1)
    else:
        print(0)