问题本质上是我发现 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];
}
问题的背景在这里：好或坏的平衡。
问题说我们有一个平衡，但我们不知道它是好是坏。我们有两种重量不同的物品，同一种物品重量相同。我们将所有项目索引到 1,2,3..n。我们随机挑选其中两个并称重。每个称重结果以 x,u,v 的形式表示，其中 x 是位指示符，0 表示平衡，1 表示不平衡，而 u 和 v 是两个项目的索引。
如果天平不好，就会出现矛盾，比如我们有这样的称量结果：
0 1 2
1 1 2
item 1 和 item 2 在两个措施中的关系不同，所以平衡不好。我需要编写一个程序来告诉最早可以确定余额是坏还是好的度量。
基本上，这是经典并集问题的变体。我希望迭代联合查找方法可以带来更好的性能，但是当递归版本被接受时，我得到了 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;
}
一个示例测试用例是
2
4 5
0 1 3
1 2 4
0 1 4
0 3 4
0 1 2
2 2
0 1 2
1 1 2