#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
/*
D=3 N
all nodes have indegree N-1
D=2
OBSERVE:
Graph is connected
if 2 nodes are not connected all other nodes are connected to them
degree in N-1 or N-2
man kann immer zwischen 2er paaren huepfen
D=1
OBSERVE
if 2 nodes are not connected all other nodes are connected to either node
find longest path ?
consider a connected component what can we say about it
can we always find a path of length == SZ(component)
connected component
add a node
if there are 2 nodes not conneced then new node also has to be connected there
GUESS
CC is fully connected besides 1 or 2 nodes
*/
std::vector<int> longest_trip(int N, int D){
vector<int> ans, rest;
int start = 0;
if(are_connected({0}, {1})){
start = 2;
}else{
start = 3;
}
ans.push_back(start%N);
for(int i=0; i<N-1; i++){
int cur = (start + i) % N, next = (start + i + 1) % N;
if(are_connected({cur}, {next})){
ans.push_back(next);
}else{
rest.push_back(next);
ans.push_back((next+1) % N);
i++;
}
}
ans.insert(ans.end(), rest.begin(), rest.end());
return ans;
}
