用 BFS 进行N叉树层序遍历算法
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 110;
int n, m;
pair<int, int> bfs(vector<vector<int>>& g) {
queue<int> q{{1}};
int level = 1;
int max_num = 1, max_level = 1;
while (not q.empty()) {
int sz = q.size();
if (sz > max_num) {
max_num = sz;
max_level = level;
}
while (sz--) {
const int cur = q.front(); q.pop();
for (const auto& child : g[cur])
q.emplace(child);
}
++level;
}
return {max_num, max_level};
}
int main(void) {
cin >> n >> m;
vector<vector<int>> g(n + 1);
while (m--) {
int id, k;
cin >> id >> k;
while (k--) {
int x;
cin >> x;
g[id].emplace_back(x);
}
}
const auto& [num, level] = bfs(g);
printf("%d %d\n", num, level);
return 0;
}
复习提高版
#include <iostream>
#define r() fast_read()
#define f(inc, frm, to) for (size_t inc = frm; inc < to; inc = -~inc)
using namespace std;
const int N = 110;
inline int fast_read(void) {
int n = 0, sign = 1;
char c = getchar();
while (c < 48 or c > 57) {
if (c == '-') sign = ~0;
c = getchar();
}
while (c >= 48 and c <= 57) {
n = (n << 1) + (n << 3) + (c ^ 48);
c = getchar();
}
return sign * n;
}
int head[N], edge_cnt;
struct Edge {
int to, nxt;
} edges[N];
inline void addEdge(int u, int v) {
edges[++edge_cnt] = {v, head[u]};
head[u] = edge_cnt;
}
int n, m;
inline void print_graph(void) {
putchar(10);
f(u, 1, n) {
printf("vertex %ld: [", u);
for (int e = head[u]; e; e = edges[e].nxt)
printf(" %d", edges[e].to);
puts(" ]");
}
}
inline void BFS(void) {
int q[N] = {1}, front = 0, rear = 1, level = 1;
int max_nodes = 0, max_level;
while (front < rear) {
size_t s = rear - front;
if (s > max_nodes) max_nodes = s, max_level = level;
while (s--) {
const int curr = *(q + front++);
for (int e = head[curr]; e; e = edges[e].nxt)
*(q + rear++) = edges[e].to;
}
++level;
}
printf("%d %d\n", max_nodes, max_level);
}
signed main(int argc, char const *argv[]) {
n = r(), m = r();
int id, k, x;
while (m--) {
id = r(), k = r();
while (k--) {
x = r();
addEdge(id, x);
}
}
BFS();
return ~~(0 ^ 0);
}