即墨做网站,浦口区网站建设技术指导,肇庆网站建设cz0758,html用什么软件编写好一点并查集#xff08;Union-Find#xff09;是一种数据结构#xff0c;它提供了处理一些不交集的合并及查询问题的高效方法。并查集主要支持两种操作#xff1a;
查找#xff08;Find#xff09;#xff1a;确定某个元素属于哪个子集#xff0c;这通常意味着找到该子集的…并查集Union-Find是一种数据结构它提供了处理一些不交集的合并及查询问题的高效方法。并查集主要支持两种操作
查找Find确定某个元素属于哪个子集这通常意味着找到该子集的“代表元素”或“根元素”。
合并Union将两个子集合并成一个集合。
并查集通过数组或树形结构来实现其中每个节点指向其父节点根节点指向自身这样形成一个或多个树形结构。每棵树代表一个集合树根的标识符通常是数组的索引代表整个集合的标识符。
基本概念 初始化开始时每个元素各自构成一个单元素集合即每个元素的父节点是其自身。 路径压缩在执行查找操作时将查找路径上的每个节点直接连接到根节点这样可以加快后续查找的速度。 按秩合并合并时总是将更小的树连接到更大的树的根节点上这可以帮助避免树变得过深从而保持操作的效率。
并查集的重要思想在于用集合中的一个元素代表集合。 现在1号和3号比武假设1号赢了这里具体谁赢暂时不重要那么3号就认1号作帮主合并1号和3号所在的集合1号为代表元素。 现在2号想和3号比武合并3号和2号所在的集合但3号表示别跟我打让我帮主来收拾你合并代表元素。不妨设这次又是1号赢了那么2号也认1号做帮主。 上面大概介绍完了整体的东西下面介绍一下细节 下面是代码部分
// 查找i的代表元素并进行路径压缩优化
int find(int i) {if (fa[i] i) // 如果元素i指向自己那么它是代表元素return i;elsereturn fa[i] find(fa[i]); // 否则递归查找并更新i的父链接为代表元素
}// 合并i和j所在的集合
void unionn(int i, int j) {int i_fa find(i); // 查找i的代表元素int j_fa find(j); // 查找j的代表元素fa[i_fa] j_fa; // 将i的集合合并到j的集合中
}find 函数通过递归查找找到一个元素的代表元素并在查找的过程中将元素直接链接到代表元素这个优化叫做路径压缩它可以减少后续查找的时间。
unionn 函数将两个元素所在的集合合并成一个集合。它首先找到每个元素的代表元素然后将其中一个集合的代表元素链接到另一个集合的代表元素上从而完成合并。这里没有实现按秩合并或路径压缩的更复杂的优化。
下面是一道题
public class UnionFind {private int[] parent;public UnionFind(int n) {parent new int[n];for (int i 0; i n; i) {parent[i] i;}}public int find(int x) {if (x ! parent[x]) {parent[x] find(parent[x]);}return parent[x];}public void union(int x, int y) {parent[find(x)] find(y);}public boolean isConnected(int x, int y) {return find(x) find(y);}public static void main(String[] args) {UnionFind uf new UnionFind(10);uf.union(0, 1); // Marry person 1 and 2uf.union(2, 3); // Marry person 3 and 4boolean areMarried uf.isConnected(1, 4); // Check if person 2 and 5 are relatedSystem.out.println(areMarried ? YES : NO); // Output should be NO if unrelated}
}
