旅行
标签 (空格分隔): noip2018 提高组
今天我给大家带来一份题解.
题目的大大致意思是这样的:
\[ 有一颗 树 / 基环树 求最小遍历顺序 \]
树的情况自然不必多讲. 做一些末端的微处理 (将每个点的邻接点排序) 即可.
而基环树呢? 这是我们就要普及一下基环树的知识了.
\[ 基环树, 简单来讲, 就是在一棵树上连一条边, 构成一个环.\]
SO
如何处理??
来, 边看代码边讲!
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn = 5e3+5;
- int n,m,x,y,dep;
- vector e[maxn]; //ling'jie'biao'cun'bian
- int tmp[maxn],ans[maxn],cnt,rd[maxn];
- bool Tre[maxn],vis[maxn],done[maxn][maxn];
- struct edge{
- int x,y;
- }del;
- void dfs(int pos){
- if(dep>n)return;
- tmp[dep]=pos;vis[pos]=1;
- for(int i=0;i<e[pos].size();i++){
- int next=e[pos][i];
- if((del.x == pos && del.y == next) || (del.x == next && del.y == pos))
- continue;
- if(!vis[next]){
- vis[next]=1;
- dep++;
- dfs(next);
- }
- }
- }
- void top(){
- queueq;
- for(int i=1;i<=n;i++){
- if(rd[i]==1){
- Tre[i]=1;
- rd[i]--;
- q.push(i);
- }
- }
- while(!q.empty()){
- int x=q.front();q.pop();
- Tre[x]=1;
- for(int j=0;j<e[x].size();j++){
- int y=e[x][j];
- rd[y]--;
- if(rd[y]==1){
- q.push(y);
- }
- }
- }
- return ;
- }
- bool check(){
- for(int i=1;i<=n;i++){
- if(ans[i] == tmp[i]){
- continue;
- }
- if(ans[i] <tmp[i]){
- return false;
- }
- if(ans[i]> tmp[i]){
- return true;
- }
- }
- }
- void update(){
- if(ans[1]==0){
- for(int i=1;i<=n;i++){
- ans[i]=tmp[i];
- }
- }
- else if(check()){
- for(int i=1;i<=n;i++){
- ans[i]=tmp[i];
- }
- }
- }
- void out(){
- for(int i=1;i<=n;i++){
- printf("%d",ans[i]);
- }
- return ;
- }
- int main(){
- scanf("%d%d",&n,&m);
- for(int i=1;i<=m;i++){
- scanf("%d%d",&x,&y);
- e[x].push_back(y);rd[y]++;
- e[y].push_back(x);rd[x]++;
- }
- for(int i=1;i<=n;i++){
- sort(e[i].begin(),e[i].end());
- }
- if(m == n-1){
- dep = 1;
- Tre[1]=true;
- dfs(1);
- update();
- }
- else {
- top();
- for(int i=1;i<=n;i++){
- if(!Tre[i]){
- for(int j=0;j<e[i].size();j++){
- if(!Tre[e[i][j]]){
- del.x = i;
- del.y = e[i][j];
- if(done[del.x][del.y]){
- continue;
- }
- done[del.x][del.y]=done[del.y][del.x]=1;
- memset(vis,0,sizeof(vis));
- vis[1]=true;dep=1;dfs(1);
- update();
- }
- }
- }
- }
- }
- out();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3107203.html