PTIT124E - Họp mặt

Link Sub: http://www.spoj.com/PTIT/problems/PTIT124E/

Người Gửi: Sai

• Problem:

Có K người (1 ≤ K ≤ 100) đứng tại vị trí nào đó trong N địa điểm cho trước (1 ≤ N ≤ 1,000) được đánh số từ 1..N. Các điểm được nối với nhau bởi M đoạn đường một chiều (1 ≤ M ≤ 10,000) (không có đoạn đường nào nối một điểm với chính nó).  

Mọi người muốn cùng tụ họp tại một địa điểm nào đó. Tuy nhiên, với các đường đi cho trước, chỉ có một số địa điểm nào đó có thể được chọn là điểm họp mặt. Cho trước K, N, M và vị trí ban đầu của K người cùng với M đường đi một chiều, hãy xác định xem có bao nhiêu điểm có thể được chọn làm điểm họp mặt.

Input

Dòng 1: Ghi 3 số: K, N, và M  Dòng 2 đến K+1: dòng i+1 chứa một số nguyên trong khoảng (1..N) cho biết địa điểm mà người thứ i đang đứng.  

Dòng K+2 đến M+K+1: Mỗi dòng ghi một cặp số A và B mô tả một đoạn đường đi một chiều từ A đến B (cả hai trong khoảng 1..N và A != B).

Output

Số địa điểm có thể được chọn là điểm họp mặt.

Example:

Input

2 4 4
2
3
1 2
1 4
2 3
3 4

Output:

2

• Solution:

Giải thích test ví dụ: có thể họp mặt tại điểm 3 và điểm 4.

Cách làm chính: "loang". - Với mỗi người sẽ loang toàn bộ các điểm mà nó có thể đến được (tư tưởng theo DFS) bằng đệ quy - Đồng thời với mỗi điểm sẽ đếm xem có bao nhiêu người duyệt qua nó. - Kiểm tra lại các điểm: Với mỗi điểm nếu đếm = K lần duyệt thì đỉnh đó có thể họp mặt đủ K người. (*Chú ý: Sử dụng danh sách kề để giảm độ phức tạp xuống còn O(max(N,M)));

• Code:

C++:

JAVA:

Author : DL

Share this

Related Posts