bfs.cpp
Bài toán
Duyệt cây theo kiểu BFS, và in ra khoảng cách từ nút 1 đến các nút khác.
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
vector<int> a[2309];
int d[2309]; //one-based
int n, m;
void bfs() {
int u, i, v;
queue<int> qu;
qu.push(1);
d[1] = 1;
while (qu.size()) {
u = qu.front();
qu.pop();
for (int i = 0; i < a[u].size(); i++) {
int v = a[u][i];
if (d[v] == 0) {
d[v] = d[u] + 1;
qu.push(v);
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
while (m--) {
int p, q;
scanf("%d%d", &p, &q);
a[p].push_back(q);
a[q].push_back(p); // remove it in one-directional graph
}
bfs();
printf(" i : ");
for (int i = 1; i <= n; i++)
printf("%3d,", i);
printf("\n");
printf("d[i] : ");
for (int i = 1; i <= n; i++)
printf("%3d,", d[i]);
printf("\n");
}
Nhận xét
Bài này cơ bản