#include "bits/stdc++.h"
using namespace std;
set<pair<int,int>> edges , bad;
map<pair<int,int>,int> mp;
set<int> adj[100001],ne[100001];
int vis[100001];
void dfs(int i){
vis[i] = 1;
for(auto j:adj[i]){
if(!vis[j]){
dfs(j);
edges.insert({i,j});
ne[i].insert(j);
ne[j].insert(i);
}else{
bad.insert({i,j});
}
}
}
vector<int> v , an;
void go(int i,int pr,int targ){
v.push_back(i);
if(i==targ){
an = v;
}
for(auto j:ne[i]){
if(j==pr)continue;
go(j,i,targ);
}
v.pop_back();
}
int qu(){
vector<int> r;
for(auto j:edges){
r.push_back(mp[j]);
}
return count_common_roads(r);
}
mt19937 rnd;
vector<int> find_roads(int n,vector<int> u,vector<int> v){
rnd.seed(n);
edges.clear();
for(int i = 0;i<n;i++){
adj[i].clear();
vis[i] =0;
}
map<pair<int,int>,int> mp;
for(int i = 0;i<u.size();i++){
adj[u[i]].insert(v[i]);
adj[v[i]].insert(u[i]);
mp[{u[i],v[i]}] = i;
mp[{v[i],u[i]}] = i;
}
set<pair<int,int>> s;
dfs(0);
int cost = qu();
while(cost<n-1){
int x = rnd()%bad.size();
auto it = bad.begin();
while(x--)it++;
pair<int,int> p = (*it);
bad.erase(it);
v.clear();an.clear();
go(p.first,-1,p.second);
x = rnd()%(an.size()-1);
pair<int,int> P = make_pair(an[x],an[x+1]);
auto IT = edges.lower_bound(P);
if(IT==edges.end()||(*IT)!=P){
swap(P.first,P.second);
IT = edges.lower_bound(P);
}
edges.erase(IT);
edges.insert(p);
int ncost = qu();
if(ncost>cost){
continue;
}else if(ncost<cost){
edges.erase(edges.lower_bound(p));
edges.insert(P);
}else{
bad.insert(P);
}
}
vector<int> r;
for(auto i:edges){
r.push_back(mp[i]);
}
return r;
}
Compilation message
simurgh.cpp: In function 'int qu()':
simurgh.cpp:37:12: error: 'count_common_roads' was not declared in this scope
37 | return count_common_roads(r);
| ^~~~~~~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int i = 0;i<u.size();i++){
| ~^~~~~~~~~
