2. 树的dfs遍历

常规
1

2. 树的dfs遍历

XJOI - 题目ID：7798必做题100分

最新提交：0 分

历史最高：0 分

时间限制: 1000ms

空间限制: 524288kB

题目描述

时间限制：1s 空间限制：512M

题目描述：

已知一棵树，有 �N 个结点，编号 11 至 �N，其中 11 号是根。

求树的深度优先搜索遍历次序。

输入格式：

第一行一个数 �N。(1≤N≤1000)

接下来 N 行每行 N 个 1 或 0，第 i 行第 j 列是 1，表示 i, j 两点有边，否则没有边。

输出格式：

深搜的次序。

样例输入：

10
0110000000
1001000000
1000110001
0100000000
0010000000
0010001000
0000010110
0000001000
0000001000
0010000000

样列输出：

1 2 4 3 5 6 7 8 9 10
2 个赞
2

这是干嘛

4 个赞
3

这个简单，你把树存一下，然后边dfs边cout当前的点

3 个赞
5

帮你格式化

#include<bits/stdc++.h>
using namespace std;
int n;
char g[1005][1005];
void dfs(int p,int m) {
	cout<<m<<" ";
	for(int j=1; j<=n; j++) {
		if(g[m][j]==‘1’&&j!=p) {
			dfs(m,j);
		}
	}
}
int main() {
	cin>>n;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			cin>>g[i][j];
		}
	}
	dfs(0,1);
	return 0;
}
4 个赞