ĐƯỜNG TRUYỀN

Xem dạng PDF

Gửi bài giải

Điểm: 10,00 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
. Đường truyền quan trọng (7 điểm).
Cho một mạng gồm tập hợp các nút và tập các đường truyền trực tiếp hai chiều nối giữa các cặp nút trong mạng. Người ta biết rằng mạng này thông suốt, tức là mọi cặp nút trong mạng đều có thể truyền tin cho nhau. 
Một số nút trong mạng cung cấp dịch vụ A còn một số nút khác cung cấp dịch vụ B cho tất cả các nút (kể cả nó). Có thể có một nút cung cấp cả hai dịch vụ. 
Nếu một đường truyền trực tiếp bị hỏng có thể làm cho một số nút trong mạng không thể sử dụng một trong hai dịch vụ. Các đường truyền như vậy được gọi  là các đường truyền quan trọng. 
Bạn hãy viết chương trình xác định số lượng đường truyền quan trọng trong mạng.
Dữ liệu vào: Cho trong file văn bản có tên  IMPONET.INP có cấu trúc:
   Dòng 1: Ghi 4 số N, M, K và L. Trong đó N là số nút trong mạng, M là số đường truyền trực tiếp trong mạng, K là số nút cung cấp dịch vụ A và L là số nút cung cấp dịch vụ B. Các nút được đánh số từ 1 đến N (1≤N≤105; 1≤M≤106; 1≤K≤N; 1≤L≤N).
   Dòng 2: Ghi K số là số hiệu các nút cung cấp dịch vụ A.
   Dòng 3: Ghi L số là số hiệu các nút cung cấp dịch vụ B.
   Trong M dòng tiếp theo, mỗi dòng ghi hai số p, q thể hiện một đường truyền trực tiếp nối nút p và nút q (1≤p, q≤N, p≠q).
(Hai số liên tiếp trên cùng một dòng được ghi cách nhau bởi ít nhất một dấu cách)

Dữ liệu ra: Ghi vào file văn bản có tên IMPONET.OUT với cấu trúc: 
   Dòng 1: Ghi một số nguyên là số lượng đường truyền quan trọng trong mạng.

Ví dụ:
IMPONET.INP     
9   10  3   4 
2   4    5  
4   9    8   3  
1   2
4   1  
2   3  
4   2  
1   5  
5   6  
6   7  
6   8  
7   9  
8   7
IMPONET.OUT
3
Giải thích
Các đường truyền quan trọng là: 
3 2 
5 6 
7 9

-------------hÕt------------


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.