Производительность метода поиска объединения, итеративный или рекурсивный

По сути, проблема в том, что я обнаружил, что рекурсивная версия метода 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

Пункт 1 и пункт 2 имеют разные отношения в двух измерениях, поэтому баланс плохой.
Мне нужно написать программу, которая скажет как можно раньше определить, что баланс плохой или хороший.

По сути, это вариация классической проблемы поиска союза.
Я ожидаю, что итеративный метод union-find может привести к повышению производительности, но я получил ограничение по времени, когда рекурсивная версия была принята. Я хочу спросить, почему это ???

И это целая версия моего алгоритма.

#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