标签: union-find

我正在使用union-find算法.在我的程序的第一部分,算法计算一个大集的分区E.

之后,我想检索S包含给定节点的集合的所有成员x.

直到现在,天真地,我正在测试E集合中所有元素的成员资格S.但昨天我正在阅读"算法导论"(由CLRS,第3版,例如21.3-4),并且在练习中,我发现:

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

" x套装成员数量的线性"对我的问题将是一个很大的改进!所以,我正在努力解决这个问题......经过一些不成功的尝试,我在Stack Overflow上寻求帮助!

我正在通过这里的排名和路径压缩来查看UnionFind与union的实现http://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_forests(它与CLRS中的伪代码几乎相同)并且不明白为什么路径压缩不会改变排名.如果我们find从根开始调用最长路径的端点,则等级应该下降,如果不是,则下一个union操作将选择不正确的根.

问题陈述:

方程以格式给出A / B = k,其中A和B是表示为字符串的变量,并且k是实数(浮点数).

给出一些查询,返回答案.如果答案不存在,则返回-1.0.

示例:给定 a / b = 2.0, b / c = 3.0.

查询是:a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? 返回 [6.0, 0.5, -1.0, 1.0, -1.0 ]

输入是:

vector<pair<string, string>> equations
vector<double>& values
vector<pair<string, string>> queries 

在哪里equations.size() == values.size(),价值是积极的.

这代表方程式.

返回vector<double>.

根据上面的例子:等式= [ ["a", …

带有着色的 DFS 将采用O(V+E)vs union find 将作为O(ElogV) 参考：http : //www.geeksforgeeks.org/detect-cycle-undirected-graph/

所以 union find 方法比较慢。如果 V = 100、E = 100、DFS = 200，则联合发现为 1,000。是否有理由使用联合查找？我个人喜欢它，因为它产生了一个干净的代码。或者我错过了什么工会发现在实际实践中更好？

给定以（A，B）形式的多个元组，其中A是二叉树中的父级，B是子级，请查找输入是否有效。提供了4个错误条件：

1. 如果父母有两个以上的孩子，
2. 如果输入了重复的元组，
3. 如果树有周期，
4. 如果可能有多个根。

如果违反多个有效条件，请按上述顺序打印条件。如果输入有效，则以串行表示形式打印树。例如：如果输入是（A，B），（B，C），（A，D），（C，E），则输出：（A（B（C（E（））））（D））

我正在考虑通过联合查找数据结构来解决它，但无法对其进行编码。谁能帮助我了解c / c ++中的逻辑或伪代码

我正在寻找工会.我想根据其中一个索引是否与另一对索引共享一个数字来对数字对进行分组.所以:

我有一对像这样的对:

pairs: [[1,3], [6,8], [3,8], [2,7]]

什么是在这样的工会中将它们分组的最佳方式:

[ [ 1, 3, 8, 6 ], [ 2, 7 ] ]

([1,3]和[3,8]一起去,因为他们共享3.该组与[6,8]结合,因为他们共享8.什么是最好的方式在javascript中这样做？

以下是其他示例:

pairs: [[8,5], [10,8], [4,18], [20,12], [5,2], [17,2], [13,25],[29,12], [22,2], [17,11]]

into [ [ 8, 5, 10, 2, 17, 22, 11 ],[ 4, 18 ],[ 20, 12, 29 ],[ 13, 25 ] ]

编辑 这是我目前使用的方法:

findUnions = function(pairs, unions){
   if (!unions){
       unions = [pairs[0]];
       pairs.shift();
   }else{
       if(pairs.length){
           unions.push(pairs[0])
           pairs.shift()
       }
   }

    if (!pairs.length){
        return unions
    }
    unite = true …

在联合查找操作的基于树的实现中，每个元素都存储在一个节点中，该节点包含指向集合名称的指针。集合指针指向 v 的节点 v 也是集合名称。每个集合都是一棵树，以具有自引用集合指针的节点为根。

要执行并集，我们只需使一棵树的根指向另一棵树的根即可。为了执行查找，我们从起始节点开始跟踪集合名称指针，直到到达集合名称指针引用自身的节点。

在按大小并集 -> 执行并集时，我们使较小树的根指向较大树的根。这意味着执行 n 个并集查找操作的时间为 O(n log n)。每次我们跟随一个指针，我们都会到达一个大小最多是前一个子树大小两倍的子树。因此，对于任何查找，我们最多都会遵循 O(log n) 个指针。

我不明白为什么对于每个联合操作，查找操作总是 O(log n)。有人可以解释一下最坏情况的复杂度是如何实际计算的吗？

我正在LeetCode上解决一个问题：

给定一个未排序的整数数组nums，返回最长连续元素序列的长度。您必须编写一个及时运行的算法O(n)。因此对于nums= [100,4,200,1,3,2]，输出为4。

解决这个问题的Union Find解决方案如下：

class Solution {
public:
    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]) {
            sz[p1]+=sz[p2];
            parent[p2]=p1;
        } else {
            sz[p2]+=sz[p1];
            parent[p1]=p2;
        }
    }

    int longestConsecutive(vector<int>& nums) {
        sz.resize(nums.size(),1);
        parent.resize(nums.size(),0);

        iota(begin(parent),end(parent),0);

        unordered_map<int, int> m;

        for(int i=0; i<nums.size(); i++) {
            int n=nums[i];
            if(m.count(n)) continue;
            if(m.count(n-1)) merge(i,m[n-1]);
            if(m.count(n+1)) merge(i,m[n+1]);
            m[n]=i; …

我想知道,为什么在union-find算法中 - 你按照它们的高度合并两棵树 - 将较小的树连接到较高的树(在没有路径压缩的简单变体中).

如果你按照元素的数量合并它们会更糟糕吗 - 用更少的元素将树用更少的元素附加到树上？

我一直在阅读有关联合查找问题的信息。两个主要的改进是路径压缩和按等级联合。据我了解，按等级联合用于确定如何组合不相交的树。如果我们有两个不相交的树 T1 和 T2，那么我们将具有较小秩的树的根附加到具有较高秩的树上。如果我们不使用路径压缩，那么等级就是树的深度。这是有道理的，因为我们不想增加输出树的深度，因为它直接影响发现和联合。

我的问题是当我们也使用路径压缩时。我一直读到这两种优化相互补充，但我没有看到。由于路径压缩，秩不再是树的深度（它成为深度的上限）。假设 T1 有 2 个分支（令 T1 的秩为 3），T2 的深度为 2，秩为 2。现在假设我们对下面标有“*”的 T1 的叶子执行查找操作（带有路径压缩）。现在，如果我们联合 T1 的根和 T2 的根，那么 T2 将附加到 T1 的根上（因为 rank 没有被 find 更新）。结果树的深度为 3。但是如果我们将 T1 附加到 T2，我们可以获得更好的性能。

T1:   o   (Rank = 3)    T2:   o  (Rank = 2)
     / \                      |
    o   o                     o
    |                         |
    o                         o
    |   
    *   

在 T1("*") 的叶子上找到后，然后在 T1 和 T2 的根上的联合我们得到

T1:    o       (Rank = 3)      T2: o  (Rank = 2)       
     /| |\                         |
    * o o o                        o …