#include "worldmap.h"
#include <algorithm>
#include <iostream>
#include <functional>
#include <utility>
#include <cmath>
std::vector<int> spanning_tree(std::vector<std::vector<int>>& adj_list) {
std::vector<std::vector<int>> edges(adj_list.size());
std::vector<std::vector<int>> adj_matrix(adj_list.size());
for (int i=0; i<adj_list.size(); i++) {
edges[i].resize(adj_list.size(), 0);
adj_matrix[i].resize(adj_list.size(), 0);
}
for (int i=0; i<adj_list.size(); i++) {
for (int j: adj_list[i]) {
adj_matrix[i][j] = 1;
adj_matrix[j][i] = 1;
}
}
std::function<bool(int, int)> dfs;
std::vector<int> visited(adj_list.size(), 0), path;
dfs = [&](int u, int p) {
if (visited[u]) return false;
visited[u] = 1;
path.push_back(u);
edges[u][p] = edges[p][u] = 1;
adj_matrix[u][p] = adj_matrix[p][u] = 0;
for (int v: adj_list[u])
if (dfs(v, u)) path.push_back(u);
return true;
}; dfs(1, 0);
// Remove redundant path
int i=path.size()-2;
for (; path[i+1] != path[i-1]; i--) {}
path.resize(i+1);
std::vector<std::vector<int>> new_adj_list(adj_list.size());
for (int i=0; i<adj_matrix.size(); i++)
for (int j=0; j<adj_matrix.size(); j++)
if (adj_matrix[i][j] && i < j)
new_adj_list[i].push_back(j);
adj_list = new_adj_list;
return path;
}
std::vector<int> get_path(std::vector<std::vector<int>>& adj_list) {
std::vector<int> spanning_path = spanning_tree(adj_list);
for (int i=0; i<adj_list.size(); i++) {
for (int j: adj_list[i]) {
bool flag = false;
std::vector<int> new_path;
for (int k: spanning_path) {
new_path.push_back(k);
if (flag) continue;
if (k == i) {
flag = true;
new_path.push_back(j);
new_path.push_back(i);
} else if (k == j) {
flag = true;
new_path.push_back(i);
new_path.push_back(j);
}
}
spanning_path = new_path;
}
}
return spanning_path;
}
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
std::vector<std::vector<int>> adj_list(N+1);
for (int i=0; i<M; i++) {
adj_list[A[i]].push_back(B[i]);
adj_list[B[i]].push_back(A[i]);
}
std::vector<int> partial = get_path(adj_list);
std::vector<std::vector<int>> ans;
for (int i=0; i<partial.size(); i++) {
ans.push_back(partial);
}
return ans;
}
