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

The_World_exe · 2020-10-21 16:46:36 · 题解

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记录是否已经回溯过。

• 1. 当前$\text{dfs}$到的点$x$不在一个环上 2. 当前$\text{dfs}$到的点$x$在一个环上

• 对于第一种情况，直接按照编号从小到大的顺序枚举x点的出边。

• 对于第二种情况，就复杂多了

  1. 对于bottom=7，因为是dfs到的第一个点，故不存在回溯操作。但是该点一定存在两个在环上的且与之相连的点4、5，将第二小的且在环上的点5记为mn，再\text{dfs}最小的点4。

     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满足以下条件则回溯：

     若以上条件均满足，则标记already=1，之后直接\text{dfs}(mn,x)就好了

     上图的例子中不存在能回溯的情况，但是样例里有qwq

     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)

     if(already==1)
      dfs(to,x);

  4. 当loop[to]=1且already=0但是又不能回溯，则说明

     • 但是需要排除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的值。

     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代码

#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;
}

原代码在原题中会WA一个点，更新后修复了这个bug。感谢 @HH_Halo