#include "worldmap.h" #include <vector> #include <map> using namespace std; map <pair<int,int>,int> mp; vector <int> gr[41]; vector <int> ans,s; int way[41][41],fix[41]; int n,k; void go(int u,int v){ int n=gr[v].size(); for (int i=0;i<n;i++){ int w=gr[v][i]; if (w!=u) { ans.push_back(v); go(v,w); } }//i if (v!=1) ans.push_back(v); } void go5(int u,int v){ fix[v]=1; for (int i=1;i<=n;i++) if (fix[i]==0 && way[v][i]==1) { ans.push_back(v); go5(v,i); } if (v!=1) ans.push_back(v); } vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) { n=N; if (M==0) { vector <vector<int>> mymap(1, std::vector<int>(1, 1)); return mymap; } // ****************** 1,2 ******************** if (M==N-1) { for (int i=1;i<=N;i++) gr[i].clear(); for (int i=0;i<M;i++){ gr[A[i]].push_back(B[i]); gr[B[i]].push_back(A[i]); } ans.clear(); go(0,1); k=ans.size(); vector<vector<int>> mymap(k, std::vector<int>(k, 1)); for (int i=0;i<k;i++) for (int j=0;j<k;j++) mymap[i][j]=ans[j]; return mymap; } else { // **************** 5 ******************** for (int i=1;i<=N;i++) { for (int j=1;j<=N;j++) way[i][j]=0; fix[i]=0; } for (int i=0;i<M;i++){ way[A[i]][B[i]]=1; way[B[i]][A[i]]=1; } ans.clear(); go5(0,1); s.clear(); mp.clear(); for (int i=1;i<=n;i++) fix[i]=0; k=ans.size(); int cnt=0; for (int i=0;i<k;i++){ s.push_back(ans[i]); if (fix[ans[i]]==0) { s.push_back(-1); s.push_back(ans[i]); fix[ans[i]]=1; cnt++; if (cnt==N) break; } } k=s.size(); vector<vector<int>> mymap(k, std::vector<int>(k, -1)); for (int i=0;i<k;i++) mymap[0][i]=s[i]; for (int u=1;u<=n;u++) for (int v=1;v<u;v++) if (way[u][v]) { pair <int,int> tmp=make_pair(v,u); if (mp[tmp]==0){ // add(v,u); int nom; for (int i=0;i<k;i++) if (mymap[0][i]==v) {nom=i; break;} for (int i=0;i<k;i++) if (mymap[i][nom+1]==-1) { mymap[i][nom+1]=u; mymap[i+1][nom]=mymap[i+1][nom+1]=mymap[i][nom]; break; } mp[tmp]=1; } }//u,v for (int i=0;i<k;i++) for (int j=0;j<k;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; }//5 }