#include "worldmap.h" #include <bits/stdc++.h> using namespace std; map<pair<int,int>, int> edge_used; vector<int> unused_graph[41], path_seq, expanded_seq; int adj[41][41], seen[41], N_global, K_global; static void build_path(int prev, int cur) { int nxt; seen[cur] = 1; for (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) { int i, j, col, v, u; N_global = N; if(M == 0) { vector<vector<int>> map_single(1, vector<int>(1, 1)); return map_single; } for(i = 1; i <= N_global; i++) { for(j = 1; j <= N_global; j++) { adj[i][j] = 0; } seen[i] = 0; } for(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(i = 1; i <= N_global; i++) { seen[i] = 0; } K_global = static_cast<int>(path_seq.size()); int unique_cnt = 0; for(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 (col = 0; col < K_global; col++) { mymap[0][col] = expanded_seq[col]; } for(u = 1; u <= N_global; u++) { for(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(i = 0; i < K_global; i++) { for(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; }