0.一些东西
原题
数据加强版
加强版代码参考你谷题解
终于调过了（又是一如既往的申必错误）
€€£ NOI plus石锤了
1.题解
原题的数据允许我们(O(n^2))暴力断边，但是加强版的数据达到了(nlog n)级别，我们必须在断边这一环节寻求更好的解法。
考虑我们进入环后在何处回溯（根据继续走环走到的点分类）：
（设当前已经从(b)走到(c)）
1.编号最小（(d<e,f)）：显然可以直接继续走；
2.编号非最大/最小（(e<d<f)）：按大小顺序走完支链再来；
3.编号最大（(d>e,f)）：需要分两种情况讨论，
①出边就是最大的（(d>b)），此时回溯更优；
②回溯后的比出边大（(b>d)），只能硬着头皮走下去。
所以说在走的时候需要记录一下最大点，这时候把边按照终点排序会很有帮助。
2.细节
1.只能回溯一次，注意标记（代码中back）；
2.注意一些功能的实现（如找环、排边等等）。
3.代码
（附注释）
（缺省源在置顶博客）
#define N 500010
int n,m,ans[N],tot,back,mx,isring;
int vis[N],rin[N],fa[N];
struct Input {
int frm,to;
Input(int _u=0,int _v=0){
frm=_u,to=_v;
}
}ipt[N<<1];
bool operator < (Input a,Input b){
return a.to>b.to;
}
struct Edge {
int to,nxt;
}e[N<<1];
int head[N],cnt;
inline void ade(int u,int v){
e[++cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
void DFS1(int now){//处理树的情况
ans[++tot]=now,vis[now]=1;
for(rg int i=head[now];i;i=e[i].nxt){
int v=e[i].to;
if(!vis[v])DFS1(v);
}
}
void DFS_Ring(int now,int ff){//找环
if(isring)return;//找到环的标记
if(!fa[now])fa[now]=ff;
else if(fa[now]!=ff){//找到环了
while(ff!=now){//不断回溯回去
rin[ff]=1;
ff=fa[ff];
}
rin[now]=isring=1;
return;
}
for(rg int i=head[now];i;i=e[i].nxt){
int v=e[i].to;
if(v!=ff)DFS_Ring(v,now);
}
}
void DFS2(int now){//处理基环树的情况
// cout<<"search "<<now<<endl;
ans[++tot]=now,vis[now]=1;
if(rin[now]){//在环上，特殊处理
int frog=0;//是否需要回溯（第三种情况）
for(rg int i=head[now];i;i=e[i].nxt){
if(back)break;//不需要回溯了
int v=e[i].to;
if(!vis[v]){
if(rin[v]){//终点在环上的出边
i=e[i].nxt;
while(vis[e[i].to])i=e[i].nxt;//不断跳访问过的
if(i)mx=e[i].to;//不是最大的出边
else if(v>mx)frog=back=1;//是最大的，回溯
//此处运用到了排序后边的顺序
break;
}
}
}
for(rg int i=head[now];i;i=e[i].nxt){
int v=e[i].to;
// printf("vis[%d]=%d,rin[%d]=%d,frog=%d
",v,vis[v],v,rin[v],frog);
if(!vis[v]){
if(!rin[v]||!frog)DFS2(v);//不需要回溯（注意||的使用）
}
}
}else {//不在环上的正常走即可
for(rg int i=head[now];i;i=e[i].nxt){
int v=e[i].to;
if(!vis[v])DFS2(v);
}
}
}
int main(){
Read(n),Read(m);
for(rg int i=1;i<=m;i++){
int u,v;
Read(u),Read(v);
ipt[i]=Input(u,v),ipt[i+m]=Input(v,u);//先存一下
}
sort(ipt+1,ipt+1+2*m);
for(rg int i=1;i<=2*m;i++)ade(ipt[i].frm,ipt[i].to);//排序后加边
if(m==n-1){
DFS1(1);
for(rg int i=1;i<=n;i++)cout<<ans[i]<<" ";
}else {
DFS_Ring(1,1);/*
for(rg int i=1;i<=n;i++){
printf("rin[%d]=%d
",i,rin[i]);
}*/
DFS2(1);
for(rg int i=1;i<=n;i++)cout<<ans[i]<<" ";
}
return 0;
}
4.完结撒花~
继续咕咕咕