本文共 2535 字，大约阅读时间需要 8 分钟。

leaned back and realized it's been a while since I last wrote anything. The pressure of not keeping up with notes has been building up, and now my mind is all over the place. Taking a full eight days off around May 1st for a mini-vacation in the珠三角 and hanging out with some friends feels like a good getaway before it all comes crashing down~

I consulted a senior from last year who got into a good school, just to get some advice on avoiding F = Fail. Turns out the main reasons were not passing the semester exams and the competition being too fierce, not participating in the fall recommendations, etc.

They say the meas exams get harder each year, even though there's this new policy about applying for读研 (master's programs) in the summer. Still, better to brush up on it just in case~

As for me, I'll start working on my thesis and some projects, counting on nobody but myself to figure things out. Only time will tell if this brings me closer to clarity.

并查集（Union-Find）是什么？

在算法和数据结构中，并查集是一个非常强大的工具，主要用于处理不相交集合（Disjoint Sets）的合并和查询操作。它通过将元素组织成树状结构来实现这一目标，每个结点都指向其父节点，同一棵树上的结点属于同一个集合。通过不断向上查找，最终能找到根节点。

并查集的核心有两个功能：

并查集的高效性在于其路径压缩和按秩合并的机制。路径压缩（Path Compression）会在查找根节点时将中间结点直接指向根节点，减少后续查找操作的开销。按秩合并（Union by Rank）则确保树的高度增长尽可能缓慢，保持操作的效率。

并查集的典型应用案例

假设有4个城市（结点）和2条已有的道路（合并操作）。这两条道路连接了以下城市：

• 0 和 2
• 3 和 2

那么，最少还需要建设多少条道路才能让这4个城市连通？

并查集实现代码

通过以下代码可以实现并查集操作：

void Initial(int n) {
    for (int i = 0; i <= n; ++i) {
        father[i] = i;
        height[i] = 0;
    }
}
int Find(int x) {
    if (x != father[x]) {
        father[x] = Find(father[x]); // 路径压缩，直接连接到根节点
    }
    return father[x];
}
void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x != y) {
        if (height[x] < height[y]) {
            father[x] = y;
        } else if (height[y] < height[x]) {
            father[y] = x;
        } else {
            father[y] = x;
            height[x]++;
        }
    }
}

代码解释

连通性问题的解决方案

在代码中，main函数从输入中读取结点数和道路数.m.初始化并查集结构后，逐一处理每条道路。最后，遍历所有结点，统计连通的集合数量。连通的集合数量减去1即为所需的最少道路数，表示将所有城市连接成一棵树所需的额外道路数。

通过这种方式，可以高效地解决连通性问题并找到最少添加的道路数。这个算法的时间复杂度接近O(.m α(n))，其中α是阿克曼函数的反函数，代表并查集操作的基数时间复杂度。