树的遍历
题意:给出谱系图(多叉树),求最多孩子的那一层的深度和宽度。
DFS遍历,记录每层的宽度,找最大的那个即可
也可以用BFS做
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
| #include <bits/stdc++.h> using namespace std; const int maxn = 100 + 10;
vector<int> tree[maxn]; int level[maxn]; bool vis[maxn];
void DFS(int root, int cnt) { level[cnt]++; for (int i = 0; i < tree[root].size(); ++i) DFS(tree[root][i], cnt + 1); }
int main(int argc, char const *argv[]) { int N, M, j = 1, cnt = 0, ans, root; cin >> N >> M; memset(vis, false, sizeof(vis)); for (int i = 0; i < M; ++i) { int ID, K, t; cin >> ID >> K; for (int j = 0; j < K; ++j) { cin >> t; tree[ID].push_back(t); vis[t] = true; } } for (int i = 1; i <= N; ++i) { if (!vis[i]) { root = i; break; } } DFS(root, 1); while (level[j] != 0) { if (level[j] > cnt) { ans = j; cnt = level[j]; } j++; } cout << cnt << " " << ans << endl;
return 0; }
|