File size: 2,216 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 | #include <bits/stdc++.h>
using namespace std;
vector<int> euler_circuit(vector<multiset<int>>& adj, int start) {
vector<int> circuit;
stack<int> stk;
stk.push(start);
while (!stk.empty()) {
int u = stk.top();
if (adj[u].empty()) {
circuit.push_back(u);
stk.pop();
} else {
auto it = adj[u].begin();
int v = *it;
stk.push(v);
adj[u].erase(it);
auto it2 = adj[v].find(u);
adj[v].erase(it2);
}
}
reverse(circuit.begin(), circuit.end());
return circuit;
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
if (N == 1) {
return {{1}};
}
vector<multiset<int>> adj(N + 1);
for (int i = 0; i < M; i++) {
int u = A[i], v = B[i];
adj[u].insert(v);
adj[u].insert(v);
adj[v].insert(u);
adj[v].insert(u);
}
int start = 0;
for (int i = 1; i <= N; i++) {
if (!adj[i].empty()) {
start = i;
break;
}
}
vector<multiset<int>> adj_copy = adj; // Copy because euler modifies
auto path = euler_circuit(adj_copy, start);
int num_traversals = 2 * M;
vector<int> seq(path.begin(), path.begin() + num_traversals);
int K = seq.size();
vector<vector<int>> C(K, vector<int>(K, 0));
for (int r = 0; r < K; r++) {
for (int c = 0; c < K; c++) {
C[r][c] = seq[c];
}
}
return C;
}
int main() {
int T;
cin >> T;
for (int t = 0; t < T; t++) {
int N, M;
cin >> N >> M;
vector<int> A(M), B(M);
for (int i = 0; i < M; i++) {
cin >> A[i] >> B[i];
}
auto C = create_map(N, M, A, B);
int K = C.size();
cout << K << endl;
for (int i = 0; i < K; i++) {
cout << K;
if (i < K - 1) cout << " ";
else cout << endl;
}
for (int r = 0; r < K; r++) {
for (int c = 0; c < K; c++) {
cout << C[r][c];
if (c < K - 1) cout << " ";
else cout << endl;
}
}
}
return 0;
} |