7714: 树的DFS序

时间限制(普通/Java):1000MS/3000MS     内存限制:65536KByte

描述

树的DFS序就是在对树进行DFS的时候，对树的节点进行重新编号，每个结点在序列中恰好出现2次。

输入

第一行为正整数n（n<=100），表示结点数。

接下来有n行，第i行的第一个数为编号为i-1的结点值（编号从0到n-1，所有值均不相同），第二个数为m，表示该结点有m个孩子，后面有m个数表示孩子结点编号。

输出

输出树的DFS序中每个结点值，兄弟结点按照输入的顺序访问。

样例输入

10
0 3 1 2 3
1 2 4 5
2 0
3 1 6
4 0
5 0
6 3 7 8 9
7 0
8 0
9 0

样例输出

0 1 4 4 5 5 1 2 2 3 6 7 7 8 8 9 9 6 3 0

从节点0开始遍历，刚访问到一个节点输出该节点值，访问完该节点相邻的所有节点后再输出一遍该节点值

代码

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 class Node//节点
 4 {
 5     public:
 6     int val;//节点值
 7     int len;//与该节点相连的个数
 8     int vec[102];/与该节点相连的每个节点编号
 9 }node[101];//每个节点
10 int n;
11 void dfs(int k)//遍历每个点
12 {
13     for(int i=0;i<node[k].len;i++)
14     {
15         cout<<" "<<node[node[k].vec[i]].val;//刚访问该节点时输出一次该节点值
16         dfs(node[k].vec[i]);
17     }
18     cout<<" "<<node[k].val;//访问完与该节点相连所有节点后输出该节点值
19 }
20 int main()
21 {
22     cin>>n;
23     for(int i=0;i<n;i++)
24     {
25         cin>>node[i].val;
26         cin>>node[i].len;
27         for(int j=0;j<node[i].len;j++)
28         {
29             cin>>node[i].vec[j];
30         }
31     }
32     cout<<node[0].val;//第一次从节点0开始访问，输出0节点值
33     dfs(0);
34     cout<<endl;
35 }