P5049 【旅行（数据加强版）】

# [P5049 旅行（数据加强版）](https://www.luogu.com.cn/problem/P5049) 这题目真的是细节超多，乍一看感觉挺简单，其实想要AC并不容易 + 在存图的时候可以采用$\text{vector}$邻接表的方式储存第$x$号点的第$i$条出边$e[x][i]$，存完后对于每一组$e[x]$按照从小到大的顺序$\text{sort}$一下，保证【编号小的边指向的点的编号】小于【编号大的边指向的点的编号】 + 之后用$\text{tarjan}$算法将整张图处理一遍，用$loop[]$数组记录一下所有在环里的点，其中$loop[i]=1$表示$i$号点在环上。在用$\text{tarjan}$算法处理整张图的过程中，用变量$bottom$表示按照顺序进行$\text{dfs}$的第一个在环中的点的编号，如下图中$bottom=7$。在之后的$\text{dfs}$过程中，用$already$记录是否已经回溯过。  + $\text{dfs}$过程中，对于当前点$x$，分成两种情况 1. 当前$\text{dfs}$到的点$x$不在一个环上 2. 当前$\text{dfs}$到的点$x$在一个环上 + 对于第一种情况，直接按照编号从小到大的顺序枚举$x$点的出边。 + 对于第二种情况，就复杂多了 1. 对于$bottom=7$，因为是$dfs$到的第一个点，故不存在回溯操作。但是该点一定存在两个在环上的且与之相连的点$4、5$，将第二小的且在环上的点$5$记为$mn$，再$\text{dfs}$最小的点$4$。 ```c++ if(x==bottom) { for(int i=0;i<e[x].size();i++) { int to=e[x][i]; if(vis[to]==1)continue; if(loop[to]==1) { kk=to; int tmp=i+1; mn=e[x][tmp]; break; } } } ``` 2. 当后续$\text{dfs}$到环上的点时，如果有一个点$x$的一条出边$i$所指向的点$to$满足以下条件则回溯： 1. $loop[to]=1$，即$to$在环上 2. $i+1=e[x].size()$，即当前出边$i$是$x$点的最后一条**有效**边（$to$是与$x$直接相连的编号最大的点）（若当前出边$i$是$x$点的倒数第二条出边，但最后一条出边指向的是上一个访问的节点满足该条件） 3. $mn<to$，即之前找到的$mn$的编号比$to$的字典序小 4. $already=0$，即之前从未回溯过 若以上条件均满足，则标记$already=1$，之后直接$\text{dfs}(mn,x)$就好了 上图的例子中不存在能回溯的情况，但是样例里有qwq ```c++ if(already==0&&mn<to&&loop[to]==1&&(i+1==e[x].size()||(i+2==e[x].size()&&e[x][i+1]==from)))//若当前出边i是x点的倒数第二条出边，但最后一条出边指向的是上一个访问的节点满足该条件 { int to=mn; already=1; dfs(to,x); } ``` 3. 当$already=1$，代表早就已经回溯过了，不能再回溯了，故直接$\text{dfs}(to,x)$ ```c++ if(already==1) dfs(to,x); ``` 4. 当$loop[to]=1且already=0$但是又不能回溯，则说明 + $x$上可能有1条或多条支链不在环上，之后的点想要回溯只能回溯到这一条有支链的点上，否则这条支链上的点就再也无法经过了。故需要更新$mn$的值：$mn=e[x][i+1]$，即在$x$的出点中选择恰好比$to$大的点作为$mn$的值。 + 但是需要排除$x$上没有支链但是$mn>to$的情况， 1. 在上图中，当$x=4,to=6$时，则更新$mn$的值，$mn=9$； 2. 当$x=6,to=8$，但是$mn=9>to$时，需要判断$[e][x][i+1]$是否为0，若$e[x][i+1]=0$说明$x$没有支链，则无需更新$mn$的值。 ```c++ else if(loop[to]==1) { int tmp=i+1; while(vis[e[x][tmp]]==1)tmp++;//避免选中已经dfs过的点 if(e[x][tmp]!=0)mn=e[x][tmp];//排除只有一条 dfs(to,x); } ``` 大概就是这么多啦，下面再贴一份AC代码 ```c++ #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #include<vector> #include<stack> using namespace std; const int N=5e5+5; int n,m; int dfn[N],low[N],vis[N]; int loop[N],bottom,mn=0x3f3f3f3f; bool looped,already; int kk; vector<int>e[N]; stack<int>s; bool cmp(int x,int y) { return x<y; } void tarjan(int x,int from,int cnt) { dfn[x]=cnt; low[x]=cnt; s.push(x); vis[x]=1; for(int i=0;i<e[x].size();i++) { int to=e[x][i]; if(to==from)continue; if(vis[to]==1) { low[x]=min(low[x],dfn[to]); looped=1; bottom=to; } else { tarjan(to,x,cnt+1); low[x]=min(low[to],low[x]); } if(looped==1)return; } if(dfn[x]==low[x]) { s.pop(); vis[x]=0; } } void get_loop() { int x; while(x!=bottom&&s.empty()!=1) { x=s.top(); s.pop(); loop[x]=1; } loop[bottom]=1; } //以下是核心部分******** void dfs(int x,int from) { bool in_loop=loop[x]; cout<<x<<" "; vis[x]=1; if(in_loop==0||already==1) { for(int i=0;i<e[x].size();i++) if(vis[e[x][i]]==0)dfs(e[x][i],x); } else if(in_loop==1) { if(x==bottom) { for(int i=0;i<e[x].size();i++) { int to=e[x][i]; if(vis[to]==1)continue; if(loop[to]==1) { kk=to; int tmp=i+1; mn=e[x][tmp]; break; } } } for(int i=0;i<e[x].size();i++) { int to=e[x][i]; if(vis[to]==1)continue; if(already==0&&mn<to&&loop[to]==1&&(i+1==e[x].size()||(i+2==e[x].size()&&e[x][i+1]==from))) { int to=mn; already=1; dfs(to,x); } else if(already==1) dfs(to,x); else if(loop[to]==1) { int tmp=i+1; while(vis[e[x][tmp]]==1)tmp++; if(e[x][tmp]!=0)mn=e[x][tmp]; dfs(to,x); } else dfs(to,x); } } } //以上是核心部分******** int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); e[u].push_back(v); e[v].push_back(u); } for(int i=1;i<=n;i++)sort(e[i].begin(),e[i].end(),cmp); tarjan(1,0,1); get_loop(); memset(vis,0,sizeof(vis)); dfs(1,1); return 0; } ``` ---- $\text{Update}\ \ 10.28$ 原代码在原题中会WA一个点，更新后修复了这个bug。感谢 @[HH_Halo ](https://www.luogu.com.cn/space/show?uid=322491)