disjoint_set并查集 桃扇骨 2021-12-12 23:43 138阅读 0赞 disjoint\_set并查集 ：可用于统计森林里有几棵树 //disjoint_set并查集 #include <iostream> using namespace std; int parent[1000]; //初始化数组 void initalise(int parent[]) { for(int i=0; i<=1000; i++) { parent[i] = i; //初始的时候每个结点都是独立的结点，其根结点就是自己 } } //查 int find_root(int x) { int z = x; //用z来预先记下待查找结点 while(x != parent[x]) { //没找到根结点，就顺着自身的父结点向上找，直至i=parent[i],此时这些结点有根结点i x = parent[x]; } //为了提高查找效率，必须做如下优化 while(z != parent[z]) { int t = z; //暂时保存开始时候查找的结点 z = parent[z];//将z指向它的前一个父结点 parent[t] = x; //将z从自己结点走到根结点的路径上的所有结点的根结点全部改为最终的根结点， //这样一来，下次查找只要从当前结点直接可以查找到根结点，不需要逐个结点挨个查找他们的父亲结点 } return x; } //查 void union_set(int a, int b) { int a_root = find_root(a); int b_root = find_root(b); parent[a_root] = b_root; //将结点a的根结点指向b的根结点即将a并入b的根结点下 } int main(){ initalise(parent); union_set(8, 2); //将8的根结点指向2 union_set(8, 3); //将8的1根结点2也指向3 , 此时2 3 8的根结点均为3 union_set(3, 9); union_set(9, 10); //此时2 3 8 9 均指向根结点10 cout << find_root(2) << " " << find_root(3) << " " << find_root(8) << endl; int sum = 0; //统计有几棵树 for(int i=1; i <= 1000; i++) { if(i == find_root(i)) { //找到了相同的根结点即为一棵树 sum++; } } cout << sum; return 0; }
相关 并查集 Ⅱ \[poj 1611\] ([http://poj.org/problem?id=1611][http_poj.org_problem_id_1611]) 题目描述： T 古城微笑少年丶/ 2022年08月03日 14:35/ 0 赞/ 253 阅读
相关 并查集 并查集JAVA版框架 并查集是一种用来管理元素分组情况的数据结构。 并查集可以高效地进行如下操作： \--查询元素a和元素b是否属于同一组 落日映苍穹つ/ 2022年06月16日 12:44/ 0 赞/ 287 阅读
相关 并查集 这个文章是几年前水acm的时候转的, 当时也不知道作者是谁, 要是有人知道的话说一下吧 并查集是我暑假从高手那里学到的一招，觉得真是太精妙的设计了。以前我无法解决的 港控/mmm°/ 2022年06月13日 14:13/ 0 赞/ 276 阅读
相关 并查集 > 题目 > 某学校近期要组织全校同学出去参加某项活动，由于人数众多，学校决定让同学们自行组队，以小组为单位进行活动。假设学校一共n个同学，每个同学有一个唯一的数字作为标签 Myth丶恋晨/ 2022年06月08日 09:24/ 0 赞/ 286 阅读
相关 并查集 森林: 森林是由若干棵互不相交的树组成,两棵树分别独立,没有交集 ![20181112082744488.png][] 并查集: 并查集的结构和森林十分相似,是 Love The Way You Lie/ 2022年04月17日 02:27/ 0 赞/ 345 阅读
相关 并查集 来看一个实例，[杭电1232畅通工程][1232] 首先在地图上给你若干个城镇，这些城镇都可以看作点，然后告诉你哪些对城镇之间是有道路直接相连的。最后要解决的是整幅图的连通性 我就是我/ 2022年03月29日 10:58/ 0 赞/ 338 阅读
相关 并查集 并查集 并查集是对树的一种操作，旨在找到某个节点的公共祖先（最老公共祖先）。我们先讲一下并。 并 并就是讲两个节点合并到一个集合里面（这个集合必须是树），每个节点 谁践踏了优雅/ 2021年12月15日 11:33/ 0 赞/ 372 阅读
相关 并查集 例题： ![输入样例][20190805122001677.png] 输入样例，第一行为一个整数n，代表有n台电脑，编号1-n；接下来进行一系列操作，当输入‘c’时，判 Dear 丶/ 2021年11月11日 08:04/ 0 赞/ 366 阅读
相关 并查集 一、算法解释 用于解决一些有N个元素的集合应用问题。 1、将每个元素初始化为自身单独成为一个集合。用p\[i\]的值表示该元素所在集合。 ![这里写图片描述][S 桃扇骨/ 2021年09月14日 02:56/ 0 赞/ 446 阅读
相关 并查集 并查集的作用就是快速判断两个元素是否在同一个集合中，快速将两个集合合并 基本模板 include <iostream> include <a 比眉伴天荒/ 2021年06月22日 15:37/ 0 赞/ 538 阅读
古城微笑少年丶
港控/mmm°
Myth丶恋晨
还没有评论，来说两句吧...