#include "worldmap.h" #include <vector> #include <map> #include <cstdlib> using namespace std; static map<pair<int,int>, int> edge_used; static vector<int> unused_graph[41]; static vector<int> path_seq; static vector<int> expanded_seq; static int adj[41][41]; static int seen[41]; static int N_global; static int K_global; static void build_path(int prev, int cur) { seen[cur] = 1; for (int nxt = 1; nxt <= N_global; ++nxt) { if (!seen[nxt] && adj[cur][nxt] == 1) { path_seq.push_back(cur); build_path(cur, nxt); } } if (cur != 1) { path_seq.push_back(cur); } } vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) { N_global = N; if (M == 0) { vector<vector<int>> map_single(1, vector<int>(1, 1)); return map_single; } for (int i = 1; i <= N_global; ++i) { for (int j = 1; j <= N_global; ++j) { adj[i][j] = 0; } seen[i] = 0; } for (int i = 0; i < M; ++i) { int x = A[i]; int y = B[i]; adj[x][y] = 1; adj[y][x] = 1; } path_seq.clear(); build_path(0, 1); expanded_seq.clear(); edge_used.clear(); for (int i = 1; i <= N_global; ++i) { seen[i] = 0; } K_global = static_cast<int>(path_seq.size()); int unique_cnt = 0; for (int i = 0; i < K_global; ++i) { int v = path_seq[i]; expanded_seq.push_back(v); if (seen[v] == 0) { expanded_seq.push_back(-1); expanded_seq.push_back(v); seen[v] = 1; ++unique_cnt; if (unique_cnt == N_global) break; } } K_global = static_cast<int>(expanded_seq.size()); vector<vector<int>> mymap(K_global, vector<int>(K_global, -1)); for (int col = 0; col < K_global; ++col) { mymap[0][col] = expanded_seq[col]; } for (int u = 1; u <= N_global; ++u) { for (int v = 1; v < u; ++v) { if (adj[v][u]) { pair<int,int> e = make_pair(v, u); if (edge_used[e] == 0) { int pos = -1; for (int idx = 0; idx < K_global; ++idx) { if (expanded_seq[idx] == v) { pos = idx + 1; break; } } if (pos != -1) { for (int row = 0; row < K_global; ++row) { if (mymap[row][pos] == -1) { mymap[row][pos] = u; mymap[row][pos - 1] = v; mymap[row + 1][pos] = v; mymap[row + 1][pos - 1] = v; break; } } } edge_used[e] = 1; } } } } for (int i = 0; i < K_global; ++i) { for (int j = 0; j < K_global; ++j) { if (mymap[i][j] == -1) { if (i == 0) { mymap[i][j] = mymap[i][j - 1]; } else { mymap[i][j] = mymap[i - 1][j]; } } } } return mymap; }