#include "simurgh.h"
#include<bits/stdc++.h>
#define pb emplace_back
#define vi vector<int>
#define pii pair<int,int>
#define fi first
#define se second
#define all(n) (n).begin(),(n).end()
using namespace std;
vi ans, pos, pos2, U, V;
int pa[505], N, M, dead[250005], deg[505];
void init(){
for(int i=0;i<N;i++) pa[i] = i;
}
int fp(int x){
if(pa[x] == x) return x;
return pa[x] = fp(pa[x]);
}
void uni(int x,int y){
x = fp(x), y = fp(y);
assert(x != y);
pa[x] = y;
}
void search_next(){
init();
random_shuffle(all(pos));
int cnt = N;
vi cur;
for(auto &i:ans){
uni(U[i], V[i]);
cur.pb(i);
cnt--;
}
vector<pii> tried;
for(auto &i:pos){
if(dead[i]) continue;
if(cnt == 2){
if(fp(U[i]) != fp(V[i])){
if(!deg[U[i]] || !deg[V[i]]) continue;
cur.pb(i);
assert(cur.size() == N-1);
int common = count_common_roads(cur);
/* cout<<common<<" "<<i<<'\n'; */
tried.pb(common,i);
cur.pop_back();
}
else pos2.pb(i);
}
else{
if(fp(U[i]) != fp(V[i])){
cur.pb(i);
uni(U[i], V[i]);
cnt--;
}
pos2.pb(i);
}
}
pair<int,int> mx = *max_element(all(tried));
if(mx.fi == (int)ans.size() - 1){
for(auto i:cur) dead[i] = 1;
}
for(auto &x : tried){
if(x.fi == mx.fi){
ans.pb(x.se);
deg[U[x.se]]--;
deg[V[x.se]]--
}
}
swap(pos, pos2);
pos2.clear();
/* for(auto i:pos) cout<<i<<" "; cout<<'\n'; */
}
// count_common_roads(vi v);
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
srand(time(0));
M = u.size(), N = n;
U = u, V = v;
for(int i=0;i<M;i++) pos.pb(i);
vi cur;
for(int i=0;i<N;i++){
cur.clear();
for(auto i:pos){
if(U[i] == i || V[i] == i) cur.pb(i);
}
deg[i] = count_common_roads(cur)
}
while(ans.size() < N - 1) search_next();
/* for(auto i:ans) cout<<i<<" "; cout<<'\n'; */
return ans;
}
Compilation message
In file included from /usr/include/c++/9/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
from simurgh.cpp:2:
simurgh.cpp: In function 'void search_next()':
simurgh.cpp:44:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
44 | assert(cur.size() == N-1);
| ~~~~~~~~~~~^~~~~~
simurgh.cpp:69:18: error: expected ';' before '}' token
69 | deg[V[x.se]]--
| ^
| ;
70 | }
| ~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:89:35: error: expected ';' before '}' token
89 | deg[i] = count_common_roads(cur)
| ^
| ;
90 | }
| ~
simurgh.cpp:91:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
91 | while(ans.size() < N - 1) search_next();
| ~~~~~~~~~~~^~~~~~~
