#include <bits/stdc++.h>
using namespace std;
struct UnionFind{
vector<int> height, parent;
void init(int n){
height.assign(n, 0);
parent.assign(n,0);
for(int i =0; i<n;i++)
parent[i] = i;
}
int getRoot(int n){
if(parent[n] != n)
return parent[n] = getRoot(parent[n]);
return parent[n];
}
bool isSame(int n1, int n2){
return getRoot(n1) == getRoot(n2);
}
void join(int n1, int n2){
int r1 = getRoot(n1);
int r2 = getRoot(n2);
if(height[r1] > height[r2]){
parent[r2] = r1;
height[r1] = max(height[r1], height[r2]+1);
}
else{
parent[r1] = r2;
height[r2] = max(height[r2], height[r1]+1);
}
}
};
vector<int> find_roads(int n, vector<int> u, vector<int> v ){
vector<int> is_royal;
int m = u.size();
set<int> dontknow;
for(int i =0; i< m; i++)
dontknow.insert(i);
/////////
while(true){
int curcheck = -1;
int prevans = -1;
int prevcheck = -1;
UnionFind uf;
uf.init(n);
vector<int> roads;
for(int i : is_royal){
uf.join(u[i], v[i]);
roads.push_back(i);
}
for(int i : dontknow){
if(!uf.isSame(u[i], v[i]) && prevcheck != i){
uf.join(u[i], v[i]);
roads.push_back(i);
curcheck = i;
if(roads.size() == n-1)
break;
}
}
int ans = grader.count_common_roads(roads);
if(ans == n-1)
return roads;
if(prevans == -1){
prevans = ans;
continue;
}
if(ans == prevans+1){
dontknow.erase(prevcheck);
is_royal.push_back(prevcheck);
}
else if(ans==prevans -1){
dontknow.erase(prevcheck);
}
prevcheck = curcheck;
}
return vector<int>();
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:70:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
70 | if(roads.size() == n-1)
| ~~~~~~~~~~~~~^~~~~~
simurgh.cpp:75:13: error: 'grader' was not declared in this scope
75 | int ans = grader.count_common_roads(roads);
| ^~~~~~
