[模板] dfs序

B.树之呼吸-贰之型-dfs序

Time Limit: 1000 MS

Memory Limit: 32768 K

Total Submit: 42 (16 users)

Total Accepted: 22 (15 users)

Special Judge: No

Description

给一棵 n 个结点的树，结点编号从 1 到 n，并指定 m 号结点为根；

请你输出这棵树长度为 2*n 的 dfs 序；

注意：在深度优先遍历面对多条分支时，请按结点编号从小到大依次遍历。

Input

输入第一行为一个正整数 T，表示测试数据组数；

对于每组测试数据，输入第一行为两个正整数 n、m，表示树的结点数及根结点的编号；

接下来 n - 1 行给出树的结构，每行两个正整数 x、y，表示结点 x 与结点 y 有边相连；

1 <= T <= 10，1 <= n <= 1e5，1 <= m <= n。

Output

每组测试数据的第一行输出“Case #i:”（不含引号），表示是第 i 组测试数据；

接下来一行输出 2*n 个正整数，表示该树的 dfs 序，用空格分隔；

行末请不要输出多余空格。

Sample Input

5 2

2 1

2 3

2 4

4 5

3 3

1 2

3 2

Sample Output

Case #1:

2 1 1 3 3 4 5 5 4 2

Case #2:

3 2 1 1 2 3

Author

陈鑫

题意: 给一棵 n 个结点的树，结点编号从 1 到 n，并指定 m 号结点为根；
请你输出这棵树长度为 2*n 的 dfs 序；
注意：在深度优先遍历面对多条分支时，请按结点编号从小到大依次遍历。
思路:dfs在进入时记录一次当前结点的下标,回溯时记录一次当前结点的下标

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<queue>
 5 using namespace std;
 6 typedef long long ll;
 7 const int amn=2e5+5;
 8 int n,m,ans=0,idx[amn],dfn[amn],cnt;
 9 vector<int> eg[amn];
10 void dfs(int x){
11     dfn[++cnt]=x;
12     idx[x]=1;
13     for(int i=0;i<eg[x].size();i++){
14         int y=eg[x][i];
15         if(idx[y])continue;
16         dfs(y);
17     }
18     dfn[++cnt]=x;
19 }
20 int main(){
21     int T,x,y;scanf("%d",&T);
22     for(int C=1;C<=T;C++){
23         for(int i=1;i<=n;i++)eg[i].clear(); ///注意vector在输入前要清空
24         scanf("%d%d",&n,&m);
25         for(int i=1;i<n;i++){
26             scanf("%d%d",&x,&y);
27             eg[y].push_back(x);
28             eg[x].push_back(y);
29         }
30         cnt=0;
31         memset(idx,0,sizeof idx);
32         dfs(m);
33         printf("Case #%d:
",C);
34         for(int i=1;i<=2*n;i++)printf("%d%c",dfn[i],i<2*n?' ':'
');
35     }
36 }
37 /**
38 题意: 给一棵 n 个结点的树，结点编号从 1 到 n，并指定 m 号结点为根；
39 请你输出这棵树长度为 2*n 的 dfs 序；
40 注意：在深度优先遍历面对多条分支时，请按结点编号从小到大依次遍历。 
41 思路:dfs在进入时记录一次当前结点的下标,回溯时记录一次当前结点的下标
42 **/