#include "icc.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 105;
int dsu[MAXN];
vector<int> S[MAXN];
/*bool G[MAXN][MAXN], done[MAXN][MAXN];
int q;
int query(int size_a, int size_b, int a[], int b[])
{
q++;
for(int i = 0; i < size_a; i++)
for(int j = 0; j < size_b; j++)
if(G[a[i]][b[j]]) return 1;
return 0;
}
void setRoad(int a, int b)
{
if(done[a][b])
{
cout << "Found edge " << a << ' ' << b << " more than once\n";
return;
}
if(G[a][b])
{
done[a][b] = done[b][a] = 1;
cout << "Correctly Found edge " << a << ' ' << b << endl;
return;
}
cout << "Wrong edge is Found " << a << ' ' << b << endl;
}*/
void merge(int a,int b)
{
int ra = dsu[a], rb = dsu[b];
if(ra == rb) return;
if(S[ra].size() > S[rb].size()) swap(ra, rb);
for(int i : S[ra])
{
S[rb].push_back(i);
dsu[i] = rb;
}
S[ra].resize(0);
}
pair<int,int> BS(vector<int> &v, int l, int r)
{
if(r - l <= 1) return {-1, -1}; // Not enough nodes to form a pair
int m = (r + l) / 2;
vector<int> first_half, second_half;
for(int i = l; i < m; i ++)
for(int j : S[v[i]])
first_half.push_back(j);
int size_f = first_half.size();
int F[size_f];
for(int i = 0; i < size_f; i++)
F[i] = first_half[i];
// from the first half is there any edge to second half
for(int i = m; i < r; i ++)
for(int j : S[v[i]])
second_half.push_back(j);
int Sec[second_half.size()];
for(int i = 0; i < second_half.size(); i++)
Sec[i] = second_half[i];
if(!query(size_f, second_half.size(), F, Sec))
{
pair<int,int> p = BS(v, l, m);
if(p.first != -1)
return p;
p = BS(v, m, r);
if(p.first != -1)
return p;
}
int s = m, e = r;
while(e - s > 1)
{
int mid = (e + s) / 2;
int size_s = 0;
for(int i = m; i < mid; i++) size_s += S[v[i]].size();
if(query(size_f, size_s, F, Sec))
e = mid;
else
s = mid;
}
int vertex = v[s];
int size_s = S[v[s]].size();
for(int i = 0; i < size_s; i++)
Sec[i] = S[v[s]][i];
s = l, e = m; // I know one of them have an edge to vertex[0];
while(e - s > 1)
{
int mid = (e + s) / 2;
int fsize = 0;
for(int i = l; i < mid; i++)
fsize += S[v[i]].size();
if(query(size_s, fsize, Sec, F))
e = mid;
else
s = mid;
}
p = {v[s], vertex};
return p; // the roots are founded
}
void run(int n)
{
for(int i = 1; i <= n; i++)
dsu[i] = i, S[i].push_back(i);
for(int i = 1; i < n; i ++)
{
vector<int> roots;
for(int v = 1; v <= n; v++)
if(dsu[v] == v)
roots.push_back(v);
// which two commponents has now merged
pair<int,int> p = BS(roots, 0, roots.size()); // returns a pair of roots that are merged
int F[S[p.first].size()], Sec[S[p.second].size()];
int sz1 = S[p.first].size(), sz2 = S[p.second].size();
for(int i = 0; i < sz1; i ++)
F[i] = S[p.first][i];
for(int i = 0; i < sz2; i ++)
Sec[i] = S[p.second][i];
int l = 0, r = sz2;
while(r - l > 1)
{
int m = (l + r) / 2;
if(query(sz1, m, F, Sec))
r = m;
else
l = m;
}
int a[] = {Sec[l]};
l = 0, r = sz1;
while(r - l > 1)
{
int m = (l + r) / 2;
if(query(m, 1, F, a))
r = m;
else
l = m;
}
setRoad(a[0], F[l]);
merge(a[0], F[l]);
}
}
/*int main()
{
int n;
cin >> n;
run(n);
return 0;
}*/
Compilation message
icc.cpp: In function 'std::pair<int, int> BS(std::vector<int>&, int, int)':
icc.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int i = 0; i < second_half.size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~~
icc.cpp:121:3: error: 'p' was not declared in this scope
121 | p = {v[s], vertex};
| ^
