BFS Cơ bản
Xem PDF
Điểm:
300 (p)
Thời gian:
1.0s
Bộ nhớ:
1023M
Input:
bàn phím
Output:
màn hình
Cho một đồ thị vô hướng gồm \(N\) đỉnh đánh số từ 1 tới \(N\) và \(M\) cạnh. Độ dài của mỗi cạnh có giá trị là 1. Một đồ thị sẽ có 1 nút trung tâm \(S\).
Yêu cầu: với mỗi đỉnh có thể tới được từ đỉnh \(S\), tính khoảng cách ngắn nhất từ đỉnh đó tới \(S\) và in ra các đỉnh theo thứ tự khoảng cách ngắn nhất tăng dần. Lưu ý: nếu 2 đỉnh có khoảng cách bằng nhau thì nhãn nào nhỏ hơn sẽ đứng trước.
Input
- Dòng đầu gồm 3 số nguyên \(N, M, S\) (\(N \leq 100000, M \leq 100000, 1 \leq S \leq N\))
- M dòng sau mỗi dòng gồm 2 số thể hiện 2 đầu của một cạnh.
Output
- In ra số dòng tương ứng với số đỉnh có thể tới được từ S theo thứ tự khoảng cách ngắn nhất tăng dần.
- Trên mỗi dòng in ra nhãn của đỉnh đó và khoảng cách ngắn nhất của đỉnh đó tới S.
Example
Test 1
Input
7 6 1
1 2
2 3
3 4
4 5
5 6
1 3 Output
1 0
2 1
3 1
4 2
5 3
6 4
Bình luận
summary
python:
from collections import deque
n, m, s = map(int, input().split())
s -= 1
edges = [[] for _ in range(n)]
d = [float('inf')] * n
dau = [0] * n
res = []
for _ in range(m):
u, v = map(int, input().split())
u -= 1
v -= 1
edges[u].append(v)
edges[v].append(u)
def bfs(source):
d[source] = 0
queue = deque([source])
dau[source] = 1
while queue:
p = queue.popleft()
for ke in edges[p]:
if dau[ke] == 1:
continue
d[ke] = min(d[ke], d[p] + 1)
queue.append(ke)
dau[ke] = 1
bfs(s)
for i in range(n):
res.append((d[i], i))
res = sorted(res)
for p in res:
if p[0] == float('inf'):
continue
print(p[1] + 1, p[0])
1 bình luận nữa