Đường đi từ S tới T và ngược lại

View as PDF

Submit solution

Points: 100.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, Alisa đang ở đỉnh T. Họ hẹn gặp vào cuối tuần ở S hoặc T. Hãy cho biết hành trình di chuyển của Jame hoặc Alisa để họ có thể gặp nhau tại S hoặc T.

Dữ liệu vào gồm:

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

Kết quả: Ghi ra các đường đi xuất phát từ đỉnh S tới T và ngược lại. Mỗi đường đi trên một hàng. Mỗi số ghi cách nhau một dấu cách. Nếu Jame và Alisa không có đường đi để gặp nhau tại S hoặc T thì ghi ra 1.

Ví dụ:
INPUT
Copy
6 11 1 6
1 3
1 2
1 5
5 1
2 6
6 2
3 2
2 4
4 2
4 6
4 5
OUTPUT
Copy
6 4 2 1
6 2 1
1 5 4 2 6

(Truy vết ngược)


Comments

Please read the guidelines before commenting.


There are no comments at the moment.