1 해설
-
1
#include<cstdio> #include<cstring> #include<iostream> #include<vector> #include<algorithm> const int Maxn = 5005; using namespace std; int cnt; int head[Maxn]; struct edge{ int u,v,next; }e[Maxn<<1]; void adde(int u,int v){ e[cnt].u=u; e[cnt].v=v; e[cnt].next=head[u]; head[u]=cnt++; } vector <int> vec[Maxn]; int n,m; int ans[Maxn]; int k[Maxn]; int x,y; int dep; bool vis[Maxn]; void dfs(int u,int fa){ if(vis[u]) return; vis[u]=1; k[++dep]=u; for(int i=0;i<vec[u].size();i++){ int v=vec[u][i]; if(v==fa) continue; if((v==y&&u==x)||(v==x&&u==y)) continue; dfs(v,u); } } bool check(){ for(int i=1;i<=n;i++){ if(k[i]==ans[i]) continue; if(k[i]>ans[i]) return false; else return true; } } void change(){ for(int i=1;i<=n;i++) ans[i]=k[i]; } //Finally u can know China Computer Federation void fuckccf(int u,int fa){ if(vis[u]) return; vis[u]=1; ans[++dep]=u; for(int i=0;i<vec[u].size();i++){ int v=vec[u][i]; if(v==fa) continue; fuckccf(v,u); } } int main(){ int u,v; memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d",&u,&v); vec[u].push_back(v); vec[v].push_back(u); adde(u,v); adde(v,u); } for(int i=1;i<=n;i++) sort(vec[i].begin(),vec[i].end()); if(n==m){ for(int i=0;i<cnt;i+=2){ dep=0;x=e[i].u;y=e[i].v; memset(vis,0,sizeof(vis)); dfs(1,-1); if(dep<n) continue; if(ans[1]==0) change(); else if(check()) change(); } for(int i=1;i<=n;i++) printf("%d ",ans[i]); return 0; } fuckccf(1,-1); for(int i=1;i<=n;i++) printf("%d ",ans[i]); return 0; }
- 1
정보
- ID
- 3950
- 시간
- 1000ms
- 메모리
- 512MiB
- 난이도
- 5
- 태그
- 제출 기록
- 13
- 맞았습니다.
- 4
- 아이디