#include "longesttrip.h"
#include <queue>
#include <stdio.h>
using namespace std;
const int MAX_N = 256;
int n;
bool inComp[MAX_N];
vector<int> adj[MAX_N];
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, c))
return getEdge(a, c);
return getEdge(a, d);
}
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);
}
vector<int> longest_trip(int N, int D) {
n = N;
for (int v = 0; v < n; v++)
inComp[v] = false;
vector<int> path(1, 0);
inComp[0] = true;
for (int i = 1; i < n; i++) {
vector<int> comp, other;
for (int v = 0; v < n; v++) {
if (!inComp[v])
other.push_back(v);
}
comp.push_back(path.back());
if ((int)path.size() > 1)
comp.push_back(path[0]);
for (int i = 1; i < (int)path.size() - 1; i++)
comp.push_back(path[i]);
if (!are_connected(comp, other)) {
if (comp.size() > other.size())
return comp;
return other;
}
pair<int, int> e = getEdge(comp, {other[0]});
inComp[e.second] = true;
int pos = 0;
while (path[pos] != e.first)
pos++;
vector<int> newPath(1, e.second);
for (int j = pos; j < (int)path.size(); j++)
newPath.push_back(path[j]);
for (int j = 0; j < pos; j++)
newPath.push_back(path[j]);
path = newPath;
}
return path;
}
