69 lines
1.8 KiB
C++
69 lines
1.8 KiB
C++
#include<bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int N = 1e5 + 10;
|
||
|
||
/*
|
||
1、一棵树的DFS序不唯一,因为深搜的时候选择哪个子节点的顺序是不一样的。
|
||
2、对于一棵树进行DFS序，需要把回溯的时候的节点编号也记录一下，这就是为什么每个数字在DFS序中会出现两遍的原因。
|
||
很容易发现的是，树的DFS序的长度是2N。
|
||
3、https://www.cnblogs.com/fusiwei/p/11758087.html
|
||
https://www.luogu.com.cn/blog/p6174/dfs-xu-ru-men
|
||
DFS序的一个性质就是把一棵子树放在一个区间里。
|
||
这个优秀的性质把树状结构变成了线性结构。方便我们进行统计。
|
||
|
||
刚刚提到的DFS序的性质让DFS序列成为了描述树的一种方式。准确地来说，
|
||
DFS序让我们把树状结构变成了一个线性的结构。我们只需要在这个线性结构上进行区间修改、
|
||
区间查询，而不需要再一遍遍地遍历整个子树来做到修改和查询。
|
||
*/
|
||
|
||
//邻接表
|
||
int idx, e[N], ne[N], h[N];
|
||
void add(int a, int b) {
|
||
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
|
||
}
|
||
|
||
int n;
|
||
int id[N];//id[] 数组就是DFS序的数组
|
||
int cnt; //cnt就是计时变量
|
||
|
||
/**
|
||
* 功能：输出dfs序
|
||
* @param u 当前结点
|
||
*/
|
||
void dfs(int u) {
|
||
id[++cnt] = u; //记录当前结点的dfs序号
|
||
for (int i = h[u]; i != -1; i = ne[i]) {//遍历当前结点的每一边条
|
||
int y = e[i];
|
||
dfs(y);
|
||
}
|
||
}
|
||
|
||
/*
|
||
9个结点8条边
|
||
测试用例
|
||
9
|
||
1 2
|
||
1 7
|
||
1 4
|
||
2 8
|
||
2 5
|
||
4 3
|
||
4 6
|
||
3 9
|
||
*/
|
||
int main() {
|
||
//邻接表初始化
|
||
memset(h, -1, sizeof(h));
|
||
|
||
cin >> n;
|
||
for (int i = 1; i < n; i++) {
|
||
int x, y;
|
||
cin >> x >> y;
|
||
add(x, y);
|
||
}
|
||
dfs(1);
|
||
for (int i = 1; i <= cnt; i++)
|
||
printf("%d ", id[i]);
|
||
return 0;
|
||
} |