对于许多问题,我看到的解决方案是使用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:
// 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; }
};
如果您愿意,请投票或接受.
