Union-find 方法性能，迭代与递归

Question

问题本质上是我发现 union-find 方法的递归版本比迭代版本更快。

// the union find method - recursive
int find(int k) {
    if(f[k] != k) f[k] = find(f[k]);
    return f[k];
}

// the union find method - iterative
int find(int k){
    while(f[k] != k) k = f[k];
    return f[k];
}

问题的上下文在这里：good or bad balance。

问题说我们有平衡，但我们不知道它是好是坏。我们有两种不同重量的物品，同一种物品具有相同的重量。我们将所有项目索引为 1,2,3..n。我们随机挑选其中两个并称量天平。每个称重结果用x,u,v的形式表示，其中x是位指标，0表示平衡，1表示不平衡，u和v是两个项目的索引。

如果天平不好，就会出现矛盾，比如我们称重的结果是这样的：

0 1 2
1 1 2

item 1和item 2在两个度量中有不同的关系，所以平衡不好。我需要编写一个程序来告诉最早可以确定余额是坏的还是余额是好的。

基本上，这是经典联合查找问题的变体。我希望迭代 union-find 方法可以带来更好的性能，但是当递归版本被接受时我得到了 Time Limit Exceeded 。我想问这是为什么？？？

这是我的算法的完整版本。

#include <iostream>
#include <vector>

using namespace std;

#define N 10009

int n, m;
int x,u,v;
vector<int> f(2*N+1,0);

// iterative
int find(int k) {
    if(k!=f[k]) f[k] = find(f[k]);
    return f[k];
}

// recursive
// int find(int k) {
//     while(k!=f[k]) k=f[k];
//     return f[k];
// }

int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    int T; // T is number of test cases
    cin >> T;
    while(T--){
        // n is number of items, m is number of measurements
        cin >> n >> m;
        f.resize(2*n+1);
        for(int i = 0 ; i < 2*n+1; ++i){
            f[i] =i;
        }

        bool flag = false;
        int ans = 0;
        int r1, r2;
        for(int i = 1 ; i <= m ; ++i){
            // x is weighing result, u and v are item id.
            cin >> x >> u >> v;
            if(flag) continue;
            if(x == 0) {
                // two items are balance
                if(find(u) == find(v+n) || find(v) == find(u+n)){
                    flag = true;
                    ans = i;
                    continue;
                }
                r1 = find(u); r2 = find(v);f[r2] = r1;
                r1 = find(u+n); r2= find(v+n); f[r2] = r1;
            } else {
                // two items are imbalance
                if(find(u) == find(v)){
                    flag = true;
                    ans = i;
                    continue;
                }
                r1 = find(u); r2= find(v+n);f[r2]=r1;
                r1 = find(v); r2 = find(u+n);f[r2]=r1;
            }               
        }
        if(flag){
            cout << "sad" << endl;
            cout << ans << endl;
        } else
            cout << "great" << endl;
    }


    return 0;
}

示例测试用例是

Answer 1

递归和迭代版本做的事情不同。递归版本将用结果更新 f[k]，因此在随后的具有相同 k 值的调用中，最多可以通过一次递归调用找到答案。如果已经找到其中一个中间值，即使在初始调用时也可以观察到这种效果。

迭代版本不更新 f 数组，因此后续调用必须执行完整循环，直到找到答案。

也有可能优化器可以内联一些递归，因此它不像最初出现的那样递归。

Union-find 方法性能，迭代与递归

Union-find method performance, iterative vs recursive

c++

iteration

algorithm

recursion

union-find