AT_abc213_d [ABC213D] Takahashi Tour 题解（图&深搜）

· · 题解

传送门

题意

有一个 n 个点的无向图。从根节点 1 开始，按如下规则遍历整个图：

  1. 如果有连接这个点的其他点没有走过，则到这个点。如果有多个点，那么按从小到大的顺序走。

  2. 如果有这个点没有其他点或者连接这个点的其他点都走过了，那么：

    • 如果这个点是根节点 1，结束。
    • 否则回到上一个点。

思路

先用 vector 存储这张图（注意是无向图）。由于要按从小到大的顺序，所以还需要进行排序。

再从根节点 1 开始深搜。用 vis 数组标记这个点有没有走过。

注意:题目要求的是遍历的过程所以返回的上一个节点编号也要输出。

代码

AC 记录

#include <bits/stdc++.h>
using namespace std;
vector<int> e[200005];
int vis[200005];
int n;
inline void dfs(int x)
{
    vis[x]=1;//标记
    cout << x << " ";
    for(int i=0;i<e[x].size();i++)
    {
        if(!vis[e[x][i]])
        {
            dfs(e[x][i]);
            cout << x << " ";//注意要输出他的上一个节点
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);//注意是无向图
    }
    for(int i=1;i<=n;i++)
    {
        sort(e[i].begin(),e[i].end());//从小到大排序
    }
    dfs(1);

    return 0;
}