BFS
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct node {
int level;
vector<int> child;
}no[100];
int num[100];
int leveltrave(int root) {
queue<int> q;
q.push(root);
no[root].level = 0;
int level;
while (!q.empty()) {
int top = q.front();
if (no[top].child.size() == 0) {
num[no[top].level]++;
}
level = no[top].level;
q.pop();
for (int i = 0; i < no[top].child.size(); i++) {
int child = no[top].child[i];
no[child].level = no[top].level + 1;
q.push(child);
}
}
return level;
}
int main() {
int n, m;
cin >> n >> m;
while (m--) {
int id, k;
cin >> id >> k;
while (k--) {
int t; cin >> t;
no[id].child.push_back(t);
}
}
int level=leveltrave(1);
for (int i = 0; i <= level; i++) {
if (i == 0) printf("%d", num[i]);
else printf(" %d", num[i]);
}
return 0;
}
DFS
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> child[100];
int num[100],maxlevel=-1;
void dfs(int root, int level) {
if (child[root].size() == 0) {
num[level]++;
maxlevel = max(maxlevel, level);
return;
}
for (int i = 0; i < child[root].size(); i++) {
dfs(child[root][i], level + 1);
}
}
int main() {
int n, m;
cin >> n >> m;
while (m--) {
int id, k;
cin >> id >> k;
while (k--) {
int t; cin >> t;
child[id].push_back(t);
}
}
dfs(1,0);
printf("%d", num[0]);
for (int i = 1; i <= maxlevel; i++) {
printf(" %d", num[i]);
}
return 0;
}
对比与总结
对比可以发现，由于BFS需要用到队列，且虽然题目不需要求解每个结点的层次，但是由于BFS不像DFS可以将level作为参数每次放在栈里面，它只能创建结构体，新增变量存放结点的level，且由于DFS采用递归，调用的是系统栈，可以省去很多代码量，明显如果BFS和DFS都能解题的情况下，DFS能简洁方便。