标签: union-find

我正在学习coursera上的算法，第一部分课程，并被困在第一个作业的奖励问题上。我已经提交了我的解决方案并获得了分数。这只是出于好奇。

反冲洗是交叉点在此图像中显示为完整（蓝色）。发生这种情况是因为我使用虚拟顶部和底部节点并连接它们下方/上方的行以满足复杂性要求；因此，将顶部连接到底部会使连接到底部的所有节点都连接到顶部。这个描述可能看起来不完整，所以我强烈建议阅读规格链接。

克服这个问题的一个解决方案是使用另一个 WeightedQuickUnion 对象并复制其中的网格而不包括底部虚拟节点。现在，此解决方案不满足评分者对奖金问题的内存要求（检查总内存 <= 11 n^2 + 128 n + 1024 字节）。我已经想到了一些解决方法（例如使用数组/堆栈来存储底行的开放站点），但所有这些方法都使用复杂度为 O(n) 的额外方法，而分配不允许这样做。根据赋值规范，除了构造函数之外，所有方法都应该有一个恒定的时间 + 对 union() 和 find() 的恒定调用次数。

我只是std::vector在这个问题中使用,我可以保证每个向量中没有重复(但每个向量中没有任何顺序).我如何结合我的载体？

例:

如果我有以下矢量......

1
1
3 2
5
5 4
2
4
4 2

在结合之后,我应该只剩下两个向量:

1
2 3 4 5

我再次使用矢量,std::set是不允许的.

我正在实现不相交的数据结构来进行联合查找.我在维基百科中看到以下声明:

......每当两个相同等级r的树结合在一起时,结果的等级为r + 1.

当树木属于同一级别时,为什么连接树的等级只增加一个？如果我只是添加两个等级(即2*r)会发生什么？

我试图在Cormen等人的算法导论中做这个练习,它与Disjoin Set数据结构有关:

假设我们希望添加操作PRINT-SET(x),该操作被赋予一个节点x并x以任何顺序打印所有成员.展示我们如何在一个不相交的林中为每个节点添加一个单独的属性,这样就PRINT-SET(x)可以在所x设置的成员数量上花费时间线性,并且其他操作的渐近运行时间不变.假设我们可以在O(1)时间内打印该组的每个成员.

现在,我非常确定所需的属性是尾指针,因此它可以跟踪孩子.

由于不相交的集合结构已经具有父属性,因此find-set(x)可以轻松地打印出一个方向上的节点.但现在,有一个尾指针,让我们走向另一个方向.

但是,我不确定如何编写算法来执行此操作.如果有人能用伪代码帮助我,那将非常感激.

我查看了其他类似的问题,但无法找出导致此错误的原因.我正在编写一个C++程序来实现Kruskal的最小生成树算法,使用Union by rank with path compression.它正确打印MST的边缘,但包括路径压缩部分导致此错误:

*./kruskal'出错:free():无效指针:0x0000000001650d00*

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, pair<int,int> > pip;
typedef pair<int,int> pii;
class UnionFind {
    vector <int> parent,rank;
    public:
        UnionFind(int n){
            parent.resize(n);
            rank.resize(n);
            for (int i=0;i<n;i++) { //initialize all parents and ranks
                parent[i]=i;
                rank[i]=0;
            }
        }
        int find (int x){
            int root=x,y;
            while (parent[root]!=root) {
                root=parent[root];
            }
//uncommenting the following loop gives the error
            /*while (parent[x]!=root){ //path compression
                y=parent[x];
                parent[x]=root;
                x=y;
            }*/
            return root;
        }
        void unite (int …

我正在学习联合/查找结构的“带路径压缩的加权快速联合”算法。普林斯顿教育网站详细解释了该算法。\n下面是 Java 的实现：

public class WQUPC {\n  private int[] id;\n  private int[] sz;\n  public WQUPC(int N) {\n    id = new int[N];\n    sz = new int[N];\n    for (int i = 0; i < N; i++) {\n      id[i] = i;\n      sz[i] = 1;\n    }\n  }\n\n  int root(int i) {\n    while (i != id[i]) {\n      id[i] = id[id[i]];\n      i = id[i];\n    }\n    return i;\n  }\n\n  boolean connected(int p, int q) { return root(p) == root(q); }\n\n  void union(int p, int …

我正在学习并查找，为了更好地理解它，我编写了一个小程序：

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
 
vector<int> parent, sz;
 
int find(int i) {
    if(parent[i]==i) return i;
    return parent[i]=find(parent[i]);
}
 
void merge(int i, int j) {
    int p1=find(i);
    int p2=find(j);
 
    if(p1==p2) return;
    if(sz[p1]<sz[p2]) {
        parent[p1]=p2;
        sz[p2]+=sz[p1];
    } else {
        parent[p2]=p1;
        sz[p1]+=sz[p2];
    }
}
 
int main() {
    vector<vector<int>> allowedSwaps={{0,4},{4,2},{1,3},{1,4}};
 
    int n=5;    //hard-code for now
    sz.resize(n,1);
    parent.resize(n);
    iota(begin(parent),end(parent),0);
 
    cout<<"Parents before: \n";
    for(auto& e: parent)
        cout<<e<<" ";
    cout<<"\n";
 
    for(vector<int>& currswap: allowedSwaps) {
        merge(currswap[0],currswap[1]);
    }
 
    cout<<"Parents after: …

我正在阅读有关着名的工会发现问题,而且这本书说:"无论是发现还是工会需要O(n)时间,而另一个需要O(1)......"

但是如何使用位串来表示集合呢？然后两个联合(使用位OR)和查找(迭代通过集合列表检查相应的位是1)将采取O(1)..

这个逻辑出了什么问题？

我正在实现Kruskal算法,这是一种众所周知的方法来查找加权图的最小生成树.但是,我正在调整它以在图表中查找周期.这是Kruskal算法的伪代码:

KRUSKAL(G):
1 A = ?
2 foreach v ? G.V:
3    MAKE-SET(v)
4 foreach (u, v) ordered by weight(u, v), increasing:
5    if FIND-SET(u) ? FIND-SET(v):
6       A = A ? {(u, v)}
7       UNION(u, v)
8 return A

我有一个很难把握FIND-SET()和MAKE-SET()功能,或者它们与并查集的实现.

我当前的代码如下所示:

class edge {
    public:      //for quick access (temp) 
      char leftV;
      char rightV;
      int weight;
};

std::vector<edge> kruskalMST(std::vector<edge> edgeList){
    std::vector<char> set;
    std::vector<edge> result;
    sortList(edgeList);    //sorts according to weight ( passed by reference)
    do{
        if(set.empty()){
            set.push_pack(edgeList[i].leftV); …

我正试图解决Union-Find这个问题

继承者删除.给定一组N个整数S = {0,1,...,N-1}和一系列以下形式的请求:

从S中删除x找到x的后继:S中的最小y,使得y≥x.设计一种数据类型,以便所有操作(构造除外)应采用对数时间或更好.

即使我找不到解决方法和文章解释如何做到这一点Union-Find,我也无法想象它是如何工作的.

例如: Delete(X)可以通过实现Union(X,X+1),但它如何作为删除我只是无法可视化.与发现相似Successor(X).

任何帮助/指导或解释的详细说明都将有很大帮助.

我正在研究通过等级和路径压缩并集的不相交算法。

我很清楚如果Union by rank使用那么find() operation复杂性是O(log(n))。

但我想知道complexity of the path compression technique如果我使用按等级并集或不使用按等级并集，不相交集算法是什么？

    int main()
    {

    char line[100];
    int N = 5;
    vector<int>adj[N];
    FILE *in = fopen("test.txt", "r");

    for (int i = 1; i <= N; i++) // Accepting the graph from file
    {
        fgets(line, 100, in);

        char *pch = strtok(line, "\t \n");
        int u = atoi(pch);

        pch = strtok(NULL, "\t \n");
        while (pch != NULL)
        {
            int v = atoi(pch);
            adj[u-1].push_back(v);
            pch = strtok(NULL, "\t \n");
        }

    }
        for( int i = 0; i < 5; i++ )  // printing the graph …