File size: 3,867 Bytes
14c9c2b | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 | #include <bits/stdc++.h>
using namespace std;
vector<vector<int>> create_map(int N, int M,
vector<int> A, vector<int> B) {
// adjacency matrix
vector<vector<bool>> adj(N+1, vector<bool>(N+1, false));
vector<vector<int>> g(N+1);
for (int i = 0; i < M; ++i) {
int a = A[i], b = B[i];
adj[a][b] = adj[b][a] = true;
g[a].push_back(b);
g[b].push_back(a);
}
// ---------- spanning tree (BFS from 1) ----------
vector<bool> vis(N+1, false);
vector<vector<int>> tree(N+1);
vector<vector<bool>> is_tree_edge(N+1, vector<bool>(N+1, false));
queue<int> q;
q.push(1);
vis[1] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : g[u]) {
if (!vis[v]) {
vis[v] = true;
tree[u].push_back(v);
tree[v].push_back(u);
if (u < v) is_tree_edge[u][v] = true;
else is_tree_edge[v][u] = true;
q.push(v);
}
}
}
// ---------- DFS traversal of the tree (start and end at 1) ----------
vector<int> seq;
function<void(int,int)> dfs = [&](int u, int p) {
seq.push_back(u);
for (int v : tree[u]) {
if (v != p) {
dfs(v, u);
seq.push_back(u);
}
}
};
dfs(1, 0);
int L = seq.size(); // L = 2*N - 1
// ---------- initial two rows ----------
vector<vector<int>> grid;
vector<vector<bool>> fixed; // which cells are not allowed to be changed
// row 0: the DFS sequence
grid.push_back(seq);
fixed.push_back(vector<bool>(L, true));
// row 1: first element 1, then seq[1..]
vector<int> row1(L);
row1[0] = 1;
for (int i = 1; i < L; ++i) row1[i] = seq[i];
grid.push_back(row1);
fixed.push_back(vector<bool>(L, true));
// ---------- collect non‑tree edges ----------
vector<pair<int,int>> non_tree;
for (int i = 0; i < M; ++i) {
int a = A[i], b = B[i];
if (a > b) swap(a, b);
if (!is_tree_edge[a][b])
non_tree.emplace_back(A[i], B[i]);
}
// ---------- place each non‑tree edge ----------
for (auto [u, v] : non_tree) {
bool placed = false;
while (!placed) {
int rows = grid.size();
vector<int>& cur_row = grid.back();
vector<bool>& cur_fixed = fixed.back();
vector<int>& prev_row = grid[rows-2]; // row above
// try to find two consecutive free cells
for (int i = 0; i < L-1; ++i) {
if (cur_fixed[i] || cur_fixed[i+1]) continue;
if (!adj[prev_row[i]][u]) continue;
if (!adj[prev_row[i+1]][v]) continue;
if (i > 0 && !adj[cur_row[i-1]][u]) continue;
if (i+1 < L-1 && !adj[v][cur_row[i+2]]) continue;
// place the edge here
cur_row[i] = u;
cur_row[i+1] = v;
cur_fixed[i] = cur_fixed[i+1] = true;
placed = true;
break;
}
if (!placed) {
// add a new row (copy of the last row, all cells changeable)
grid.push_back(grid.back());
fixed.push_back(vector<bool>(L, false));
}
}
}
// ---------- make the grid square ----------
int R = grid.size();
int C = L;
int K = max(R, C);
// extend rows by duplicating the last row
while ((int)grid.size() < K) {
grid.push_back(grid.back());
}
// extend columns by duplicating the last column of each row
for (int i = 0; i < K; ++i) {
while ((int)grid[i].size() < K) {
grid[i].push_back(grid[i].back());
}
}
return grid;
} |