NOIP2018 旅行

题目大意：求一棵树的最小DFS序，和一张n条边的连通图删去任意一条边以后的最小DFS序。
话说这一题和我出过的某一道题非常神似，都是在求一些特定的DFS序。就连对DFS的描述也和我的描述非常相似。
所以在考场上我用了几分钟的时间概括出了简要题面，然后用了十分钟写掉了。
第一个子问题很简单，贪心地DFS即可，这是因为字典序的特性，使得，如果每一次拓展都选择的是当前最小的，那么总是不会更劣。
对于第二个子问题，它不再是求纯粹的DFS序了，但是看到\(n=5000\)的数据范围，可以想到暴力枚举删边，这就转化为第一个问题。
如果依然是一边DFS一边删边的话，最坏情况下可能会达到\(O(n^2*logn)\)的复杂度，尽管有32Gi7，也很难通过一些大数据。
我们考虑预处理。首先将读入的边排序，然后插入边表。这样遍历的顺序就是从小到大了。
注意对边进行预排序时，由于插入边表是倒序插入，所以应当让末端点从大到小排序。
这就做完了。

#include<iostream>
#include<cstdio>
#include<algorithm>
int n,m;
struct ee{
	int v;
	int nxt;
}e[10005];
int h[5005],et=0;
inline void add(int u,int v){
	e[++et]=(ee){v,h[u]};
	h[u]=et;
}
struct e0{
	int u;
	int v;
	bool operator<(const e0 &B)const{
		return (u==B.u)?(v>B.v):(u<B.u);
	}
}e0[10005],e00[5005];
int Du,Dv,ans[5005],Ans[5005],at=0;
bool vis[5005];
inline void dfs(int X){
	vis[X]=1,ans[++at]=X;
	for(int i=h[X];i;i=e[i].nxt){
		if(vis[e[i].v]||(e[i].v==Du&&X==Dv)||(e[i].v==Dv&&X==Du)){
			continue;
		}
		dfs(e[i].v);
	}
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d%d",&e0[i].u,&e0[i].v);
		e00[i].u=e0[i].u,e00[i].v=e0[i].v;
		e0[i+m].u=e0[i].v,e0[i+m].v=e0[i].u;
	}
	std::sort(e0+1,e0+(m<<1|1));
	for(int i=1;i<=(m<<1);++i){
		add(e0[i].u,e0[i].v);
	}
	if(m==n-1){
		Du=0,Dv=0;
		dfs(1);
		for(int i=1;i<=n;++i){
			printf("%d ",ans[i]);
		}
		return;
	}else if(m==n){
		for(int i=1;i<=n;++i){
			Ans[i]=0x3f3f3f3f;
		}
		for(int i=1;i<=m;++i){
			Du=e00[i].u,Dv=e00[i].v;
			at=0;
			for(int j=1;j<=n;++j){
				vis[j]=0;
			}
			dfs(1);
			if(at==n){
				for(int j=1;j<=n;++j){
					if(ans[j]==Ans[j]){
						continue;
					}else if(ans[j]>Ans[j]){
						break;
					}else{
						for(int k=1;k<=n;++k){
							Ans[k]=ans[k];
						}
						break;
					}
				}
			}
		}
		for(int i=1;i<=n;++i){
			printf("%d ",Ans[i]);
		}
	}
}
int main(){
	init();
	return 0;
}