Tìm điểm hẹn

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 ở đâu đó trong đồ thị. Hãy tìm các đỉnh mà Jame và Alisa có thể di chuyển tới để họ có thể gặp nhau. Tất nhiên, 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, 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 các điểm hẹn tìm được. Các đỉnh được sắp xếp thành dãy tă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 thì ghi ra -1.

Ví dụ:
INPUT
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
1 2 4 6

Comments

Please read the guidelines before commenting.


There are no comments at the moment.