Đường truyền an toàn DFSSAFE

View as PDF

Submit solution

Points: 200.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Đồ thị có hướng là đồ thị mà tất cả các cạnh trong đồ thị có hướng. Cạnh (u, v) thể hiện chỉ có đường đi từ đỉnh u tới đỉnh v. Cho đồ thị có hướng có N đỉnh, M cạnh. Jame đang ở đỉnh S, muốn truyền tin đến đỉnh T. Đường truyền được gọi an toàn khi có ít nhất hai đường truyền khác nhau từ đỉnh S đến đỉnh T. Hai đường truyền được gọi là khác nhau khi đi có ít nhất một đỉnh trên đường đi khác nhau. Hãy cho biết đường truyền từ S tới T có an toàn hay không? Nếu có ghi ra YES và số lượng đường chuyền từ S tới T, ngược lại ghi ra NO.

Dữ liệu:

  • Dòng 1: Ghi số nguyên dương N, M, S, T (M, N ≤ 3000, S, T ≤ N, S≠T).
  • M dòng tiếp theo, mỗi dòng ghi số nguyên dương u và v thể hiện có đường đi từ đỉnh u đến đỉnh v (u, v ≤ N).

Kết quả: Ghi ra nếu đường truyền từ S tới T là an toàn thì ghi ra YES và số lượng đường truyền từ S tới T, ngược lại ghi ra NO.

Ví dụ:
input:
6 11 1 6
1 3
1 2
1 5
5 1
2 6
6 2
3 2
2 4
output:
YES 2

Comments

Please read the guidelines before commenting.


There are no comments at the moment.