河南专业网站建设公司排名,最近七天的新闻大事,百度指数api,wordpress设置文章页1.并查集的概论 定义#xff1a; 并查集是一种树型的数据结构#xff0c;用于处理一些不相交集合的合并及查询问题#xff08;即所谓的并、查#xff09;。比如说#xff0c;我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。 主要构成#xff1a; …
1.并查集的概论 定义 并查集是一种树型的数据结构用于处理一些不相交集合的合并及查询问题即所谓的并、查。比如说我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。 主要构成 并查集主要由一个整型数组pre[ ]和两个函数find( )、join( )构成。 数组 pre[ ] 记录了每个点的前驱节点是谁函数 find(x) 用于查找指定节点 x 属于哪个集合函数 join(x,y) 用于合并两个节点 x 和 y 。 作用 并查集的主要作用是求连通分支数如果一个图中所有点都存在可达关系直接或间接相连则此图的连通分支数为1如果此图有两大子图各自全部可达则此图的连通分支数为2…… 2.用一个故事来引入并查集“魔法学院的联盟”
在遥远的阿尔多王国有一座声名远扬的魔法学院——天星学院。这所学院不仅教授强大的魔法还拥有许多古老的传说。传说中提到曾经有一个神秘的魔法师名叫艾尔文他发明了一种神奇的魔法工具叫做“并查集”。
故事发生在天星学院的一个风和日丽的早晨学院的学生们正忙于准备即将到来的年度魔法比赛。比赛的内容是让学生们组成小组进行各种挑战争夺“学院最佳团队”的荣誉。
艾伦和他的朋友们被分配到了同一个小组但在比赛前的准备中他们发现学院里有多个小组已经相互合作形成了若干个强大的联盟。这些联盟的存在让他们感到有些困惑因为他们不知道如何将所有的合作伙伴都联系起来从而提高自己的团队实力。
就在他们为此感到苦恼时学院的长者向他们介绍了一种古老的魔法——并查集。长者解释说并查集是一种强大的魔法工具可以帮助他们轻松地管理和合并不同的联盟。
艾伦和他的朋友们认真听取了长者的讲解并决定尝试使用这种魔法。他们发现并查集的核心在于两个主要操作
合并Union当两个小组决定合作时他们可以通过这个操作将两个小组合并成一个更强大的联盟。查找Find当他们需要知道某个小组是否已经与其他小组在同一个联盟中时可以使用这个操作来检查。
使用了并查集的魔法后艾伦和他的团队发现管理各个小组变得更加简单。他们能够迅速地找到已经存在的联盟并根据需要进行合并。这使得他们能够更好地协调和组织自己的资源形成了一个强大的联盟。
随着比赛的进行艾伦和他的团队利用并查集的魔法成功地将所有的小组整合到一起形成了一个无敌的联盟。他们在比赛中表现出色最终赢得了“学院最佳团队”的荣誉。
在获胜的庆祝会上艾伦和他的朋友们感慨万千他们深刻理解了并查集魔法的强大力量也明白了团队合作的重要性。从那以后天星学院的学生们都学会了如何使用并查集来解决各种复杂的联盟问题而艾伦和他的团队也因为这次经历成为了学院的传奇人物。
3.从数据结构的方向看并查集 查找Find确定一个元素属于哪个集合通常返回集合的代表元素或根节点。此操作可以通过路径压缩优化使得树的高度保持较小从而提高查找效率。 合并Union将两个集合合并为一个集合。合并操作可以通过按秩合并按树的深度合并或按大小合并合并小的树到大的树来优化从而保持数据结构的效率。
并查集常用于处理动态连通性问题例如在图论中的连通分量计算。通过这些操作并查集能够在接近常数时间内完成集合的合并和查找。
3.find函数的定义与实现
find() 函数用于确定一个元素所在的集合的代表元素或根节点。它通常通过路径压缩优化来提高效率。 开始时每个集合都是一个独立的集合,并且都是等于自己本身下标的数 例如: p[5]5,p[3]3; 如果是M操作的话那么就将集合进行合并,合并的操作是: p[3]p[5]5; 所以3的祖宗节点便成为了5 此时以5为祖宗节点的集合为{53} 如果要将p[9]9插入到p[3]当中,应该找到3的祖宗节点, 然后再把p[9]9插入其中,所以p[9]find(3);(find()函数用于查找祖宗节点) 也可以是p[find(9)]find(3),因为9的节点本身就是9 此时以5为祖宗节点的集合为{5,3,9}; 如果碰到多个数的集合插入另一个集合当中其原理是相同的 例如: 上述中以5为祖宗节点的是p[5],p[3],p[9];(即p[5]5,p[3]5,p[9]5) 再构造一个以6为祖宗节点的集合为{6,4710} 如果要将以6为祖宗节点的集合插入到以5为祖宗节点的集合,则该操作可以是 p[6]find(3)或者find(9),find(5) 此时p[6]5 当然如果是以6为祖宗节点集合中的4,7,10则可以这样 p[find(4)]find(3) 或者p[find(7)]find(3)均可以 此时以6为祖宗节点的集合的祖宗节点都成为了5 3.2find函数的实现 第一个find函数同时也运用了状态压缩即 find 函数不仅有找祖宗的功能还把这个查找路径上所有节点直接变成了祖宗节点的孩子 int find(int x)
{if(p[x]!x) p[x]find(p[x]);/*经上述可以发现,每个集合中只有祖宗节点的p[x]值等于他自己,即:p[x]x;*/return p[x];//找到了便返回祖宗节点的值
}2.
int find(int x) //查找x的祖宗结点
{while(pre[x] ! x) //如果x的上级不是祖宗节点x pre[x]; //x继续找return x;
}4.合并集合的代码实现与逻辑 先查找两个元素 x 和 y 的根节点。比较两个根节点的秩高度将秩较小的根节点的树合并到秩较大的根节点的树下确保树的高度尽可能低。如果两个根节点的秩相同将其中一个根节点设置为另一个根节点的子节点并将该根节点的秩加一。 //合并a b所在的两个集合
void merge(int a, int b)
{int pa find(a);//找到 a 所在集合的代表元素int pb find(b);//找到 b 所在集合的代表元素if(pa ! pb)//如果不是同一个则属于不同集合需要合并{p[pa] pb;//将a所在集合代表元素的代表元素设置为b所在集合的代表元素。}
}
5.并查集的测试代码进行了按秩合并的写法
#include vector
#include iostreamclass DisjointSet {
public:DisjointSet(int size) : parent(size), rank(size, 1) {// 初始化每个元素的父节点指向自己for (int i 0; i size; i) {parent[i] i;}}// 查找元素 x 所在集合的根节点并进行路径压缩int find(int x) {if (parent[x] ! x) {parent[x] find(parent[x]); // 路径压缩}return parent[x];}// 合并两个集合void unionSets(int x, int y) {int rootX find(x); // 查找 x 的根节点int rootY find(y); // 查找 y 的根节点if (rootX ! rootY) {// 按秩合并将秩较低的树合并到秩较高的树下if (rank[rootX] rank[rootY]) {parent[rootY] rootX;} else if (rank[rootX] rank[rootY]) {parent[rootX] rootY;} else {parent[rootY] rootX;rank[rootX] 1;}}}private:std::vectorint parent; // 记录每个元素的父节点std::vectorint rank; // 记录每个树的秩
};int main() {DisjointSet ds(10); // 初始化一个包含10个元素的并查集ds.unionSets(1, 2); // 合并集合 {1} 和 {2}ds.unionSets(2, 3); // 合并集合 {1, 2} 和 {3}ds.unionSets(4, 5); // 合并集合 {4} 和 {5}// 检查合并后的结果std::cout Find 1: ds.find(1) std::endl; // 输出 1std::cout Find 3: ds.find(3) std::endl; // 输出 1std::cout Find 4: ds.find(4) std::endl; // 输出 4std::cout Find 5: ds.find(5) std::endl; // 输出 4ds.unionSets(3, 5); // 合并集合 {1, 2, 3} 和 {4, 5}// 检查合并后的结果std::cout Find 5 after union with 3: ds.find(5) std::endl; // 输出 1因为 1 和 5 现在在同一集合中return 0;
}6.简单的实现代码没有使用按秩合并的写法
#include vector
#include iostreamclass DisjointSet {
public:DisjointSet(int size) : parent(size) {for (int i 0; i size; i) {parent[i] i; // 每个元素的父节点初始化为自身}}// 查找元素 x 所在集合的根节点并进行路径压缩int find(int x) {if (parent[x] ! x) {parent[x] find(parent[x]); // 路径压缩}return parent[x];}// 合并 a 和 b 所在的两个集合void merge(int a, int b) {int rootA find(a); // 查找 a 所在集合的代表元素int rootB find(b); // 查找 b 所在集合的代表元素if (rootA ! rootB) {parent[rootB] rootA; // 直接将 b 的根节点挂到 a 的根节点下}}private:std::vectorint parent; // 记录每个元素的父节点
};int main() {DisjointSet ds(10); // 初始化一个包含10个元素的并查集ds.merge(1, 2); // 合并集合 {1} 和 {2}ds.merge(2, 3); // 合并集合 {1, 2} 和 {3}ds.merge(4, 5); // 合并集合 {4} 和 {5}// 检查合并后的结果std::cout Find 1: ds.find(1) std::endl; // 输出 1std::cout Find 3: ds.find(3) std::endl; // 输出 1std::cout Find 4: ds.find(4) std::endl; // 输出 4std::cout Find 5: ds.find(5) std::endl; // 输出 4ds.merge(3, 5); // 合并集合 {1, 2, 3} 和 {4, 5}// 检查合并后的结果std::cout Find 5 after union with 3: ds.find(5) std::endl; // 输出 1因为 1 和 5 现在在同一集合中return 0;
}7.一些基本操作的实现
const int N1005 //指定并查集所能包含元素的个数由题意决定
int pre[N]; //存储每个结点的前驱结点
int rank[N]; //树的高度
void init(int n) //初始化函数对录入的 n个结点进行初始化
{for(int i 0; i n; i){pre[i] i; //每个结点的上级都是自己 rank[i] 1; //每个结点构成的树的高度为 1 }
}
int find(int x) //查找结点 x的根结点
{if(pre[x] x) return x; //递归出口x的上级为 x本身则 x为根结点 return find(pre[x]); //递归查找
} int find(int x) //改进查找算法完成路径压缩将 x的上级直接变为根结点那么树的高度就会大大降低
{if(pre[x] x) return x; //递归出口x的上级为 x本身即 x为根结点 return pre[x] find(pre[x]); //此代码相当于先找到根结点 rootx然后 pre[x]rootx
} bool isSame(int x, int y) //判断两个结点是否连通
{return find(x) find(y); //判断两个结点的根结点即代表元是否相同
}bool join(int x,int y)
{x find(x); //寻找 x的代表元y find(y); //寻找 y的代表元if(x y) return false; //如果 x和 y的代表元一致说明他们共属同一集合则不需要合并返回 false表示合并失败否则执行下面的逻辑if(rank[x] rank[y]) pre[y]x; //如果 x的高度大于 y则令 y的上级为 xelse //否则{if(rank[x]rank[y]) rank[y]; //如果 x的高度和 y的高度相同则令 y的高度加1pre[x]y; //让 x的上级为 y}return true; //返回 true表示合并成功
}
