宁波高端网站开发,厦门网站设计哪家公司好,展示型网站,温州seo关键词1. 解决什么问题#xff1f;
当题目最终要将数据分成若干个集合时#xff0c;可往并查集的方向思考。并查集三个字拆开对应“合并”#xff0c;“查找”#xff0c;“集合”#xff0c;这样就很好理解了。 【思路】
为了方便查找和合并#xff0c;每个元素都有对应的代…1. 解决什么问题
当题目最终要将数据分成若干个集合时可往并查集的方向思考。并查集三个字拆开对应“合并”“查找”“集合”这样就很好理解了。 【思路】
为了方便查找和合并每个元素都有对应的代表元素代表元素就是它所在集合里的所有元素的代表元素。
因此要构建一个 father 数组 表示每个元素的代表元素。 2. 模板
1构建集合/初始化
一开始每个元素就是自己的代表元素后续根据题目要求进行合并如果要求集合的个数也可以在此处表示。
也不一定写成函数此处只是为了方便展示。
void build(int n)
{for (int i 1; i n; i)father[i] i;sets n;
} 2查找递归思路
如果 i father[i] 则 i 为代表元素。
而当一个元素的 father 不是本身时则再找 father 的 father知道找到代表元素为止。
int find(int p)
{if (father[p] ! p){father[p] find(father[p]);}return father[p];
} 3合并
将代表元素合并也就是相当于两个集合合成一个集合 void set_union(int x, int y){int fx find(x);int fy find(y);if (fx ! fy){father[fx] fy;sets--;}} 3. 优化
一般的并查集用上面的模板就可以如果想更快些可以看下面的版本但需要的空间会大些
1扁平化
【思路】
因为 find 方法调用频繁所以如果将递归的次数减少一些会大大优化时间复杂度
优化方法就是将同一代表元素的元素的 father 都改成代表元素(原先是通过递归来实现的)
【实现方式】
需要开一个栈来实现栈来收集从该元素到代表元素沿途的元素再将他们的 father 一一改成代表元素
而当下次再调用时就可以只循环一次找到它的 father。
int find(int i) {int size 0;while (i ! father[i]) {stack[size] i;i father[i];}while (size 0) {father[stack[--size]] i;}return i;
} 2小挂大
需要多开一个数组表示代表元素对应的集合的元素个数记为 size 数组初始化时全为1
两个集合合并表示为对应代表元素的 size 值小的加到大的上
void set_union(int × int y)
{int fx find(x);int fy find(y);if (fx ! fy) {// 小的挂在大的上if (size[f×] size[fy]) {size[f×] size[fy];father[fy] fx;} else {size[fy] size[f×];father[fx] fy;}}
} PS如果看模板不好理解最好结合练习看会舒服很多 4. 练习
1模板题
链接牛客_并查集的实现 2相似字符串组
链接leet_839
【分析】
核心思路就是并查集通过记录每个字符串的不同字符数找相似字符串然后按并查集的思路合并最终输出集合的个数。
【参考代码】链接 3情侣牵手
链接leet_765
【分析】
情侣数一定是人数的一半故只需开人数一半的集合即可规定其 ID 对应除以2的数就是对应的情侣 ID
那么每一次相邻两个元素合并就将其情侣 ID (可理解为代表元素)合并即可因为在合并的函数中属于相同集合的不用再进行操作而只有不是属于一个集合的才减少集合的个数
【参考代码】链接
