#include "worldmap.h" #include <cassert> #include <cstdio> #include <bits/stdc++.h> using namespace std; vector<int>j; map<pair<int,int>,int>mp; //const int N1=50; vector<int>v[500]; //#include "worldmap.h" int x[500]; int yuuu; int bati[500][500]; void dfs(int a,int parent){ x[a]=1; for(int i=0; i<=yuuu; i++){ if(x[i]==0 && bati[a][i]==1){ j.push_back(a); dfs(i,a); } } if(a!=1){ j.push_back(a); } } vector<vector<int>>create_map(int N, int M,vector<int> A,vector<int> B) { int n=M; if(M==N-1){ for(int i=0; i<=N; i++){ v[i].clear(); } j.clear(); int n=A.size(); for(int i=0; i<n; i++){ v[A[i]].push_back(B[i]); v[B[i]].push_back(A[i]); } for(int i=1; i<=N; i++) x[i]=0; dfs(1,0); for(int i=1;i<=N; i++) if(x[i]==0)dfs(i,0); int batiii=j.size(); vector<vector<int>> ans(batiii, vector<int>(batiii)); for(int i=0; i<j.size(); i++){ for(int drnachvi=0; drnachvi<j.size(); drnachvi++){ ans[drnachvi][i]=j[i]; //cout<<ans[drnachvi][i]<<" "; } //cout<<endl; } return ans; exit(0); } else{ for(int i=0; i<=N; i++){ v[i].clear(); } yuuu=N; j.clear(); for(int i=0; i<=N; i++){ for(int j=0; j<=N; j++){ bati[i][j]=0; } } for(int i=0; i<M; i++){ v[A[i]].push_back(B[i]); v[B[i]].push_back(A[i]); bati[A[i]][B[i]]=1; bati[B[i]][A[i]]=1; } for(int i=0; i<500; i++){ x[i]=0; } j.clear(); dfs(1,0); for(int u=1; u<=N; u++) if(x[u]==0) dfs(u,0); // for(auto a:j){ // cout<<a<<" "; // } // cout<<endl; vector<int>drnachvi; drnachvi.clear(); mp.clear(); int ku=j.size(); int mtvleli=0; int zuigetsu[N+1]; for(int i=0; i<=N; i++){ zuigetsu[i]=0; } for(int i=0; i<M; i++){ // v[A[i]].push_back(B[i]); // v[B[i]].push_back(A[i]); bati[A[i]][B[i]]=1; bati[B[i]][A[i]]=1; } for(int i=0; i<j.size(); i++){ drnachvi.push_back(j[i]); if(zuigetsu[j[i]]==0){ drnachvi.push_back(-19); drnachvi.push_back(j[i]); zuigetsu[j[i]]=1; mtvleli++; if(mtvleli==N)break; } } if(mtvleli<N){ for(int u=1; u<=N; ++u){ if(zuigetsu[u]==0){ drnachvi.push_back(u); drnachvi.push_back(-19); drnachvi.push_back(u); zuigetsu[u]=1; mtvleli++; if(mtvleli==N) break; } } } int batiii=drnachvi.size(); vector<vector<int>> ans(batiii, vector<int>(batiii,-19)); for(int i=0; i<batiii; i++){ ans[0][i]=drnachvi[i]; } for(int i=1; i<=N; i++){ for(int j=1; j<i; j++){ if(bati[i][j]==1){ pair<int,int>p={i,j}; if(mp[p]==0){ int maomao=-1; for(int juuu=0; juuu<batiii; juuu++){ if(drnachvi[juuu]==j){ maomao=juuu; break; } } if(maomao!=-1){ maomao++; for(int ka=0; ka<batiii; ka++){ if(ans[ka][maomao]==-19){ ans[ka][maomao]=i; ans[ka][maomao-1]=j; if(ka<batiii-1){ ans[ka+1][maomao]=j; ans[ka+1][maomao-1]=j; } break; } } } mp[p]=1; } } } } for(int i=0; i<batiii; i++){ for(int j=0; j<batiii; j++){ if(ans[i][j]==-19){ if(i==0){ if(j>0)ans[i][j]=ans[i][j-1]; else ans[i][j]=1; } else ans[i][j]=ans[i-1][j]; } } } // if(ans.size()>2){ // vector<vector<int>>ixvi(ans.size()-2, vector<int>(ans.size()-2)); // for(int i=0; i<ans.size()-2; i++){ // for(int j=0; j<ans.size()-2; j++){ // ixvi[i][j]=ans[i][j]; // } // } // return ixvi; // } // else return ans; return ans; } }