东平可信的网站建设,代替wordpress,备案的时候网站名称,东莞前十的外贸公司典型例题 Acwing 权值
故名思义#xff0c;在带权并查集中#xff0c;我们需要让每个节点携带一个**“权值”**。 那么这个权值应该是什么呢#xff1f;其实答案就在并查集当中。 由于在并查集当中我们可以在 O ( 1 ) O(1) O(1) 时间内找到一个节点的根节点#xff0c;那…典型例题 Acwing 权值
故名思义在带权并查集中我们需要让每个节点携带一个**“权值”**。 那么这个权值应该是什么呢其实答案就在并查集当中。 由于在并查集当中我们可以在 O ( 1 ) O(1) O(1) 时间内找到一个节点的根节点那么我们可以让这个权值表示为某个节点到根节点的距离。
如何维护权值
首先我们需要一个“懒标记数组 d d d”至于为什么称其为“懒标记”稍后再解释。这个数组就是用来记录我们权值的数组。 即 d [ i ] d[i] d[i] 表示 i i i 到根节点的距离。 其次我们需要在 f i n d find find 函数中做一点手脚。这个也稍后解释
懒标记数组和find()
明明就是用来维护权值的数组为什么我们要称其为懒标记呢 试想一下当我们将以 f b fb fb 为根的集合添加到以 f a fa fa 为根的集合的尾部我们是需要修改以 f b fb fb 为根的子树集合里面所有点的 d [ ] d[] d[] 的是不是想象就可怕呢 好现在我们试着正经分析一下如果我们真的要一次性修改以 f b fb fb 为根的子树集合中的所有点有什么办法可以得到这些点吗 贪心的想我们肯定希望直接找到集合中的所有点然后修改但这是不可能的由于我们在并查集中只能找到根节点而不能从根节点找孩子节点所以我们只能遍历所有点判断每一个点所在的集合是否为 f b fb fb这么做的时间复杂度为 O ( N ) O(N) O(N)如果执行 N N N 次这样的操作就是平方级别的复杂度这肯定无法接受 但我们又无法回避这个问题该如何做呢 – 参考线段树中懒标记的做法 当我们需要修改以 f b fb fb 为根的集合中所有点的权值时我们只修改该集合根节点 f b fb fb 的权值然后其余的点我们不做操作 等我们对集合中的某个点 x x x不是该集合的根节点 执行 f i n d find find 操作时 f i n d find find 会找到 x x x 的所有父节点直到根节点。 我们发现我们找到了一条从直接从底层节点到根节点的路径并且寻找这个路径的过程是递归的线性 既然递归的路径是从底到根那么回溯时的路径必然是从根到底而从根到底的过程就可以找到根的所孩子这些孩子就是该根所在集合中的子树节点 这个时候回溯就可以用来修改我们的懒标记将他们变成正确的值。 并且从根到底的回溯也能保证答案的正确性因为当某个节点的根被修改时它所有的子节点也需要修改子树的值依赖于它的根的值因此保证根的正确性才能保证底的正确性。 例如我们让根节点指向一个新的根节点那么不仅原来的根节点的 d [ ] d[] d[] 变化了它的所有子节点的 d [ ] d[] d[] 也需要变化。 最后还有一个疑问如果你每次 f i n d ( x ) find(x) find(x) 都会修改 x x x 到树根的路径上的 d d d那么会不会导致一个点被重复多次修改导致它的 d [ ] d[] d[] 比实际更大呢 答案是不会的因为在第一次 f i n d ( x ) find(x) find(x) 之后 x x x 会因为路径压缩直接指向树的根节点这样当下一次再 f i n d ( x ) find(x) find(x) 时会直接返回 p r e [ x ] pre[x] pre[x]不会涉及到清除懒标记修正它的 d [ ] d[] d[]这一步。
图解 顺便解释一下清除懒标记修正 d [ ] d[] d[]的公式d[x] d[x] d[pre[x]] 具体含义一个节点到根节点的距离 它到父节点的距离 父节点到根节点的距离 因此在修正一个节点 x x x 时我们需要先修正它的父节点 p r e [ x ] pre[x] pre[x] 到树根的 d [ p r e [ x ] ] d[pre[x]] d[pre[x]]这一点从公式也可以清晰的看出 这也就是我们在 f i n d ( x ) find(x) find(x) 中 int root find(pre[x]); 做的事情如果写的更清楚一点那就是
int find(int x)
{if(pre[x] x) return x; // 原本的findfind(pre[x]); // 1. 先修正所有祖先节点(父-根)s[x] s[x] s[pre[x]]; // 2. 修正自己return pre[x] find(pre[x]); // 原本的find
}可以发现不过是比原本的路径压缩 f i n d find find 多了两条语句罢了如果我们把最后一句return pre[x] find(pre[x]); 再优化一下那就是下面的形式不过该优化对时间效率的提升很小因为在我们执行 find(pre[x]) 之后 p r e [ x ] pre[x] pre[x] 便已经直接指向根节点 r o o t root root这样当我们下次再执行 f i n d ( p r e [ x ] ) find(pre[x]) find(pre[x]) 时由于已经路径压缩过了实际查找速度是 O ( 1 ) O(1) O(1) 的。
int find(int x)
{if(pre[x] x) return x;int root find(pre[x]); // 1. 先修正所有祖先节点(父-根)s[x] s[x] s[pre[x]]; // 2. 修正自己return pre[x] root;
}代码
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 30010;int pre[N];
int d[N], s[N];
// s[i] 表示 i 所在集合中点的个数
// d[i] 标识 i 到其集合中根节点的距离带有懒标记的权值数组int find(int x)
{// 当 pre[x] x即该节点就是集合的根节点时// 不存在岁回溯路径也就不需要也不能去除懒标记if(pre[x] x) return x;// 存在回溯路径去除懒标记// 先递归一直找到根节点int root find(pre[x]); // 从根节点开始往下回溯d[x] d[pre[x]]; // d[x]_new d[x]_old d[pre[x]];参考上面的图 return pre[x] root; // 别忘了路径压缩
}void merge(int a, int b)
{int fa find(a), fb find(b);if(fa fb) return ;// 可以合并// 只修改a的根节点fapre[fa] fb;d[fa] s[fb];// 修改集合大小s[fb] s[fa];
}int main()
{for(int i 0; i N; i ){pre[i] i;s[i] 1;d[i] 0; // 初始状态时自己就是自己的根节点}int T; cin T;while(T -- ){string op; int a, b;cin op a b;if(op M) merge(a, b);else {int fa find(a), fb find(b);if(fa ! fb) cout -1 endl;// 注意a和b可能相等的情况else cout max(0, abs(d[a] - d[b]) - 1) endl;}}return 0;
}2024/3/11
#include iostream
#include algorithm
#include cstringusing namespace std;const int N 30010;int pre[N], d[N], cnt[N];int find(int x)
{if(pre[x] x) return x;int root find(pre[x]);d[x] d[x] d[pre[x]];return pre[x] root;
}int main()
{for(int i 0; i N; i ) pre[i] i, cnt[i] 1;int q; cin q;while(q -- ){string op; int a, b;cin op a b;int fa find(a), fb find(b);if(op M){if(fa ! fb){pre[fa] fb;d[fa] cnt[fb];cnt[fb] cnt[fa];}}else {if(fa ! fb) cout -1 endl;else {if(a b) cout 0 endl;else cout abs(d[a] - d[b]) - 1 endl;}}}return 0;
}
