【ETOJ P1021】树的遍历 题解（有向图+深度优先搜索+广度优先搜索）

题目描述

给定一棵大小为 $n$，根为 $1$ 的树，求出其按照 dfs 和 bfs 进行遍历时的顺序。

请将所有出点按照编号从小到大排序后进行遍历。

dfs 为深度优先搜索，bfs 为宽度优先搜索。

输入格式

一个整数 $n$，表示点的个数。$(1\le n\le 50)$

接下来一行 $n-1$ 个整数，表示点 $2\sim n$ 的父亲 $f{a}_i$。$(1\le f{a}_i\le n)$

输出格式

第一行输出 dfs 时的顺序，第二行输出 bfs 时的顺序。

样例输入1

4
1 1 2

样例输出1

1 2 4 3
1 2 3 4

样例输入2

5
1 2 2 4

样例输出2

1 2 3 4 5
1 2 3 4 5

---

思路

数组 fa 来存储每个节点的父节点，向量数组 edges 来存储图的边。

在 main 函数中，首先读取节点的数量 n，然后读取每个节点的父节点，将每个节点添加到其父节点的边列表中。接着，对每个节点的边列表进行排序，以保证遍历的顺序。

调用 dfs 函数进行深度优先搜索。在 dfs 函数中，首先将起始节点压入栈 s1，然后在栈不为空的情况下，弹出栈顶元素，打印其值，然后将其所有子节点（除去父节点）压入栈 s2。接着，将 s2 中的所有节点都压入 s1，这样就实现了深度优先的遍历顺序。

调用 bfs 函数进行广度优先搜索。在 bfs 函数中，首先将起始节点加入队列 q1，然后在队列不为空的情况下，弹出队首元素，打印其值，然后将其所有子节点（除去父节点）加入队列。这样就实现了广度优先的遍历顺序。

---

AC代码

#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#define AUTHOR "HEX9CF"
using namespace std;const int N = 1e3 + 7;int n;
int fa[N];
vector<int> edges[N];void dfs(int x) {stack<int> s1;stack<int> s2;s1.push(x);while (s1.size()) {int t = s1.top();s1.pop();cout << t << " ";for (auto &i : edges[t]) {if (i == fa[t]) {continue;}s2.push(i);}while (s2.size()) {s1.push(s2.top());s2.pop();}}
}void bfs(int x) {queue<int> q1;q1.push(x);while (q1.size()) {int f = q1.front();q1.pop();cout << f << " ";for (auto &i : edges[f]) {if (i == fa[f]) {continue;}q1.push(i);}}
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for (int i = 2; i <= n; i++) {cin >> fa[i];edges[fa[i]].push_back(i);}for (int i = 1; i <= n; i++) {sort(edges[i].begin(), edges[i].end());}dfs(1);cout << endl;bfs(1);cout << endl;return 0;
}