#include "worldmap.h" #include <bits/stdc++.h> using namespace std; int fix[245]; vector <vector <int> > build_mst(int N, const vector<vector<int> >& v) { vector <vector <int> > mst(N + 1); vector <int> visited(N + 1, 0); queue<int> q; visited[1] = 1; q.push(1); while(!q.empty()) { int u = q.front(); q.pop(); for(int j = 0; j < v[u].size(); j++) { if(!visited[v[u][j]]) { visited[v[u][j]] = 1; mst[u].push_back(v[u][j]); mst[v[u][j]].push_back(u); q.push(v[u][j]); } } } return mst; } void DFS(int u, int parent, const vector<vector<int> >& mst, vector<int>& order) { order.push_back(u); for(int j = 0; j < mst[u].size(); j++) { if(mst[u][j] != parent) DFS(mst[u][j], u, mst, order); } } vector <vector <int> > create_map(int N, int M, vector<int> A, vector<int> B) { int i, j, k, ind; vector < vector <int> > v(N + 1); vector <int> order; if(M == 0) { vector <vector<int> > mymap(1, std::vector<int>(1, 1)); return mymap; } for(i = 1; i <= N; i++) { v[i].clear(); } order.clear(); for(i = 0; i < M; i++) { v[A[i]].push_back(B[i]); v[B[i]].push_back(A[i]); } vector <vector <int> > mst = build_mst(N, v); DFS(1, -1, mst, order); vector <vector <int> > mymap(order.size() * 3, std::vector<int>(order.size() * 3, 0)); k = order.size() * 3; ind = 0; for(i = 0; i < k; i++) { if(i % 3 == 0) { for(j = 0; j < k; j++) { mymap[i][j] = order[ind]; } ind++; } } for(i = 0; i < k; i++) { if(i % 3 == 2) { for(j = 0; j < k; j++) { mymap[i][j] = mymap[i - 2][j]; } } } for(i = 0; i < k; i++) { if(i % 3 == 1) { for(j = 0; j < v[mymap[i - 1][0]].size() * 2; j++) { if(j % 2 == 0) mymap[i][j] = mymap[i - 1][0]; else mymap[i][j] = v[mymap[i - 1][0]][j / 2]; } } } for(i = 0; i < k; i++) { for(j = 0; j < k; j++) { if(mymap[i][j] == 0) mymap[i][j] = mymap[i - 1][j]; } } return mymap; }