精选文章 - 算法学习第28天｜Algorithm Picks

今日精选｜Today’s Picks

📌 文章推荐｜Recommended Reading

并查集（Union-Find）完全指南

并查集是一种处理不相交集合（Disjoint Sets）合并与查询的数据结构，核心操作只有两个：Find（查集）和 Union（合并）。在解决连通性问题（Connected Components）时表现出色，典型应用包括 Kruskal 最小生成树算法、网络连接判断、朋友圈问题等。

Union-Find is a data structure designed for managing disjoint sets with just two core operations: Find (path compression) and Union (by rank or size). It excels at solving connectivity problems — from Kruskal’s MST algorithm to social circle detection.

💡 核心要点｜Key Concepts

1. 路径压缩（Path Compression）：在 Find 过程中将路径上所有节点的父节点直接指向根节点
2. 按秩合并（Union by Rank）：合并时让较小的树接到较大的树下，保持结构平衡
3. 复杂度：近乎 O(α(n))，α 为 Ackermann 函数的反函数，近似常数

🔗 LeetCode 练习题｜Practice Problems

• 1. 岛屿数量（Number of Islands）
• 1. 省份数量（Number of Provinces）
• 1. 冗余连接（Redundant Connection）
• 1. 连通网络的操作次数

每天进步一点点，一年后的你会感谢现在努力的自己。 A small daily improvement compounds over time. Be proud of today’s work. 💪