Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

STNODE - VOI09 Nút st - xung yếu

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/stnode


Bản đồ giao thông của hành tinh X bao gồm n thành phố được đánh số từ 1 đến n và m đoạn đường một chiều nối các cặp thành phố, giữa hai thành phố bất kỳ có không quá một đoạn đường cùng chiều nối chúng. Thành phố s là thủ đô của hành tinh, từ đó có thể di chuyển theo các đoạn đường nối giữa các thành phố để đến bất cứ thành phố nào trong số các thành phố còn lại. Thành phố t là một điểm du lịch ưa thích của người dân thủ đô. Hàng năm có một lượng lớn người dân thủ đô đến nghỉ ngơi tại điểm du lịch hấp dẫn này. Vì thế, trong các mùa du lịch ách tắc giao thông trên đường đi từ s đến t thường xuyên xảy ra tại một số nút giao thông. Do đó, Bộ Giao thông của hành tinh X muốn xác định các nút giao thông này. Ta nói thành phố a ( a ≠ s và a ≠ t) là nút st-xung yếu nếu mọi đường đi từ s đến t đều phải đi qua a.

Yêu cầu: Hãy xác định số lượng các nút st-xung yếu.

Dữ liệu:

  • Dòng đầu tiên chứa 4 số nguyên dương n, m, s, t (3 ≤ n ≤ 104, m ≤ 105);
  • m dòng tiếp theo mô tả sơ đồ giao thông trên hành tinh X: Dòng thứ i chứa hai số nguyên ui, vi cho biết có đoạn đường một chiều đi từ thành phố ui đến thành phố i, i = 1, 2, ..., m. Các số liên tiếp trên cùng dòng được ghi cách nhau bởi ít nhất một dấu cách.

Kết quả

  • Một số nguyên duy nhất là số lượng nút st-xung yếu.

Ví dụ

Dữ liệuKết quả
7 10 1 5
1 2
1 3
2 4
3 4
4 5
5 6
6 2
6 7
7 3
7 5
1
Ràng buộc: 60% số tests ứng với 60% số điểm của bài có 3 ≤ n ≤ 100.

Được gửi lên bởi:VOJ problem setters
Ngày:2009-02-26
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Thi HSG Quốc gia 2009

hide comments
2018-07-17 13:59:18
DFS: 75
BFS: 90
BFS + DFS: 100
2017-12-07 09:45:07
DFS được 75 ai biết tại sao chỉ vs
2017-11-30 10:30:02
nhật hào sạch
2017-10-04 09:35:55
Code AC: http://123link.top/STNODE
2017-09-29 11:41:19
qua don gian

2017-08-21 15:54:59
khao khảo thuật toán và code:
https://vietcodes.github.io/code/50/
2017-07-31 04:43:38
100 diem ac
http://ideone.com/yUmgJ8

Last edit: 2017-07-31 04:44:26
2017-07-28 05:50:29
Code AC: http://shink.in/cIWht
2017-06-06 04:35:44
.

Last edit: 2017-06-06 04:36:09
2017-02-06 09:30:50
83,33 ai chỉ vs
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.