联合查找数据结构 [英] Union-find data structure

问题描述

对于许多问题，我看到解决方案是使用union-find数据结构。我试图阅读它，并考虑如何实现（使用C ++）。我目前的理解是，它只不过是一套集合。所以要找到属于哪一个元素，我们需要 n * log n 操作。当我们必须执行工会时，我们必须找到需要合并的两个集合，并对它们执行一个 set_union 。这对我来说看起来并不高效。我对这个数据结构的理解是正确的还是我缺少某些东西？

解决方案

这是很晚的回复，但这可能不是在stackoverflow上的其他地方已被回答，由于这是搜索union-find的人的最多页面，这里是详细的解决方案。

Find-Union是一个非常快速的操作，在几乎不变的时间内执行。
它遵循Jeremie对路径压缩和跟踪集合大小的见解。对每个查找操作本身执行路径压缩，从而获得lg *（n）的摊销时间。 lg *就像逆Ackerman函数一样，生长非常慢，很少超过5（至少直到n <2 ^ 65535）。联合/合并集执行懒惰，只需将1根指向另一个根，特别是较小的集合的根到较大集的根，它在不间断的时间完成。

请参阅以下代码从 https://github.com/kartikkukreja/blog-codes/blob/master/src/Union%20Find%20%28Disjoint%20Set% 29％20Data％20Structure.cpp

  class UF {
 int * id，cnt，* sz ; 
 public：
 //使用N个隔离集创建一个空联合查找数据结构。 
 UF（int N）{
 cnt = N; id = new int [N]; sz = new int [N]; （int i = 0; i< N; i ++）id [i] = i，sz [i] = 1的
 } 
〜UF（）{delete [] id;删除[] sz; } 
 
 //返回对应于对象p的组件的id。 
 int find（int p）{
 int root = p; 
 while（root！= id [root]）root = id [root]; 
 while（p！= root）{int newp = id [p]; id [p] = root; p = newp; } 
返回根; 
} 
 //用它们的联合替换包含x和y的集合。 
 void merge（int x，int y）{
 int i = find（x）; int j = find（y）; if（i == j）return; 
 //使较小的根点更大一个
 if（sz [i]< sz [j]）{id [i] = j，sz [j] + = sz [i]; } 
 else {id [j] = i，sz [i] + = sz [j]; } 
 cnt--; 
} 
 //对象x和y在同一个集合？ 
 bool connected（int x，int y）{return find（x）== find（y）; } 
 //返回不相交集的数量。 
 int count（）{return cnt; } 
}; 
  

如果您愿意，请投票或接受。

For many problems I see the solution recommended is to use a union-find data structure. I tried to read about it and think about how it is implemented (using C++). My current understanding is that it is nothing but a list of sets. So to find which set an element belongs we require n*log n operations. And when we have to perform union, then we have to find the two sets which needs to be merged and do a set_union on them. This doesn't look terribly efficient to me. Is my understanding of this data structure correct or am I missing something?

解决方案

This is quite late reply, but this has probably not been answered elsewhere on stackoverflow, and since this is top most page for someone searching for union-find, here is the detailed solution.

Find-Union is a very fast operation, performing in near constant time. It follows Jeremie's insights of path compression, and tracking set sizes. Path compression is performed on each find operation itself, thereby taking amortized lg*(n) time. lg* is like the inverse Ackerman function, growing so very slow that it is rarely beyond 5 (at least till n< 2^65535). Union/Merge sets is performed lazy, by just pointing 1 root to another, specifically smaller set's root to larger set's root, which is completed in constant time.

Refer the below code from https://github.com/kartikkukreja/blog-codes/blob/master/src/Union%20Find%20%28Disjoint%20Set%29%20Data%20Structure.cpp

class UF {
  int *id, cnt, *sz;
  public:
// Create an empty union find data structure with N isolated sets.
UF(int N) {
    cnt = N; id = new int[N]; sz = new int[N];
    for (int i = 0; i<N; i++)  id[i] = i, sz[i] = 1; }
~UF() { delete[] id; delete[] sz; }

// Return the id of component corresponding to object p.
int find(int p) {
    int root = p;
    while (root != id[root])    root = id[root];
    while (p != root) { int newp = id[p]; id[p] = root; p = newp; }
    return root;
}
// Replace sets containing x and y with their union.
void merge(int x, int y) {
    int i = find(x); int j = find(y); if (i == j) return;
    // make smaller root point to larger one
    if (sz[i] < sz[j]) { id[i] = j, sz[j] += sz[i]; }
    else { id[j] = i, sz[i] += sz[j]; }
    cnt--;
}
// Are objects x and y in the same set?
bool connected(int x, int y) { return find(x) == find(y); }
// Return the number of disjoint sets.
int count() { return cnt; }
};

Kindly up-vote or accept if you like.

这篇关于联合查找数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！