#include "stations.h"
#include <vector>
#include <algorithm>
void dfs(std::vector<std::vector<int> > &graph, std::vector<int> &labels, int p, bool nodeType, int &clock) {
labels[p] = -1;
if(nodeType == true) {
labels[p] = clock;
clock++;
}
for(int q:graph[p]) {
if(labels[q] == -2) {
dfs(graph,labels,q,!nodeType,clock);
}
}
if(nodeType == false) {
labels[p] = clock;
clock++;
}
return;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
//graph transformation
std::vector<std::vector< int > > graph(n);
for(int i=0;i<n-1;i++) {
graph[u[i]].push_back(v[i]);
graph[v[i]].push_back(u[i]);
}
std::vector<int> labels(n,-2);
//labeling process
bool initNode = true;
int clock = 0;
dfs(graph,labels,0,initNode,clock);
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
//finding out the node type
std::sort(c.begin(),c.end());
int degree = c.size();
int fatherNode;
if(s < c[0]) {
//s is labeled by arrival time
fatherNode = c[degree - 1];
if(t < s || t > fatherNode) {
//should be sent to father node
return fatherNode;
}
int dest = -1;
for(int q:c) {
if(t <= q && dest == -1) {
dest = q;
}
}
return dest;
}
else {
//s is labeled by departure time
std::reverse(c.begin(),c.end());
fatherNode = c[degree - 1];
if(t > s || t < fatherNode) {
//should be sent to father node
return fatherNode;
}
int dest = -1;
for(int q:c) {
if(t >= q && dest == -1) {
dest = q;
}
}
return dest;
}
}
