并查集用vector实现路径压缩find和按秩合并unionSet：初始化parent[i]=i、rank全0；find递归压缩路径；unionSet先判同根，再按秩合并，秩等时新根秩+1。
用 vector 实现带路径压缩的 find 和按秩合并的 unionSet
并查集核心就两个操作：找根（find）和合并（unionSet）。C++ 里最常用的是用 vector 存父节点，下标是节点编号，值是它的直接父节点。初始化时每个点指向自己：parent[i] = i。
路径压缩在 find 里做：递归找到根后，把沿途所有节点的父指针直接连到根上。按秩合并（rank）避免树退化成链表——只把矮树挂到高树下。注意 rank 不是真实高度，只是上界估计，所以叫“秩”更准确。
class UnionFind {
vector<int> parent, rank;
public:
UnionFind(int n) : parent(n), rank(n, 0) {
for (int i = 0; i <h3>为什么不用 <code>map</code> 存非连续编号节点？</h3>
<p>如果节点编号稀疏或不是整数（比如字符串 ID），确实有人想用 <code>map<string string></string></code> 或 <code>unordered_map</code>。但这样会带来三个实际问题：</p>
<ul>
<li>
<code>find</code> 递归调用时哈希查找开销变大，路径压缩收益被抵消</li>
<li>无法预分配空间，<code>rank</code> 也得用 <code>map</code> 维护，逻辑变重</li>
<li>很多题目输入保证编号是 <code>0..n-1</code>，强行用 <code>map</code> 属于过早优化</li>
</ul>
<p>真要处理字符串节点，先离散化映射到 <code>0..k-1</code> 再用 <code>vector</code> 版本，比全程哈希快且稳。</p>
<h3>
<code>unionSet</code> 里漏判 <code>rx == ry</code> 会导致什么？</h3>
<p>常见错误是合并前没检查是否已同属一个集合，直接执行 <code>parent[ry] = rx</code>。后果是：</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/gongju/2823" title="C++14"><img
src="https://img.php.cn/upload/manual/001/431/639/6ac8b33c327c4749.png" alt="C++14" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="overflowclass">C++14</a>
<p class="overflowclass">C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。</p>
</div>
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<ul>
<li>可能把某棵树的根错误地设为自己子节点（比如 <code>rx == ry</code> 时 <code>parent[rx] = rx</code> 看似无害，但后续 <code>rank</code> 更新会错乱）</li>
<li>如果代码里有计数逻辑（如维护连通分量数量），不提前 <code>return</code> 就会多减一次</li>
<li>某些 OJ 题目卡常，重复合并会拖慢 <code>find</code> 效率（虽然路径压缩能缓解，但没必要）</li>
</ul>
<p>所以 <code>if (rx == ry) return;</code> 这行不能省，它不是防御性编程，而是逻辑必需。</p>
<h3>静态数组 vs <code>vector</code>：竞赛和工程场景怎么选？</h3>
<p>算法题里一律用 <code>vector</code>，因为大小在运行时才知道；但嵌入式或性能极端敏感场景，可能用 <code>std::array</code> 或裸数组（如 <code>int parent[100005]</code>）。</p>
<p>关键区别在于：</p>
<ul>
<li>
<code>vector</code> 构造/析构有少量开销，但支持动态扩容（虽然并查集不需要）</li>
<li>裸数组必须编译期确定大小，写死上限容易溢出，写太大又浪费内存</li>
<li>
<code>std::array</code> 折中，但无法传参推导大小，接口不如 <code>vector</code> 自然</li>
</ul>
<p>除非明确知道最大节点数且对启动时间极度敏感，否则别为了省几十纳秒改用静态数组——调试成本和可读性损失更大。</p></int>
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
