#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 256;
int n;
vector<int> comp[MAX_N];
int parent[MAX_N];
bool inPath[MAX_N];
mt19937 rnd(200);
int findParent(int v) {
if (parent[v] != v)
parent[v] = findParent(parent[v]);
return parent[v];
}
void connect(int u, int v) {
u = findParent(u);
v = findParent(v);
if (u == v)
return;
for (int x: comp[v])
comp[u].push_back(x);
comp[u].clear();
parent[v] = u;
}
pair<int, int> getEdge(vector<int> a, vector<int> b) {
if (a.size() == 1 && b.size() == 1)
return {a[0], b[0]};
vector<int> c, d;
if (a.size() == 1) {
for (int i = 0; i < (int)b.size() / 2; i++)
c.push_back(b[i]);
for (int i = (int)b.size() / 2; i < (int)b.size(); i++)
d.push_back(b[i]);
if (are_connected(a, d))
return getEdge(a, d);
return getEdge(a, c);
}
for (int i = 0; i < (int)a.size() / 2; i++)
c.push_back(a[i]);
for (int i = (int)a.size() / 2; i < (int)a.size(); i++)
d.push_back(a[i]);
if (are_connected(c, b))
return getEdge(c, b);
return getEdge(d, b);
}
pair<int, int> getEdgeBrute(vector<int> a, vector<int> b) {
for (int u: a) {
for (int v: b) {
if (are_connected(a, comp[v]))
return getEdge({u}, comp[v]);
}
}
return {0, 0};
}
void shiftRight(vector<int> &v) {
int aux = v.back();
for (int i = v.size() - 1; i >= 1; i--)
v[i] = v[i - 1];
v[0] = aux;
}
void check(vector<int> v) {
for (int i = 0; i < (int)v.size() - 1; i++)
assert(are_connected({v[i]}, {v[i + 1]}));
}
vector<int> longest_trip(int N, int D) {
n = N;
vector<int> perm(n, 0);
for (int i = 0; i < n; i++) {
perm[i] = i, parent[i] = i;
comp[i].clear();
comp[i].push_back(i);
inPath[i] = false;
}
shuffle(perm.begin(), perm.end(), rnd);
vector<int> path(1, perm[0]);
inPath[perm[0]] = true;
while ((int)path.size() < n) {
vector<int> allOut, cliqueOut;
for (int v = 0; v < n; v++) {
if (inPath[v])
continue;
if (findParent(parent[v]) == v)
cliqueOut.push_back(v);
allOut.push_back(v);
}
if (!are_connected({path.back()}, allOut)) {
if (!are_connected(path, allOut)) {
if (path.size() > allOut.size())
return path;
return allOut;
}
auto e = getEdge(path, allOut);
if (e.first == path[0])
reverse(path.begin(), path.end());
else {
while (path.back() != e.first)
shiftRight(path);
}
path.push_back(e.second);
inPath[e.second] = true;
for (int v: allOut) {
if (v != e.second) {
path.push_back(v);
inPath[v] = true;
}
}
continue;
}
auto e = getEdgeBrute({path.back()}, cliqueOut);
for (int v: comp[e.second]) {
path.push_back(v);
inPath[v] = true;
}
}
return path;
}
