MẠNG MÁY TÍNHMỘT MẠNG GỒM N MÁY TÍNH ĐÁNH SỐ TỪ 1 ĐẾN N, VÀ M K...

Bài 2. Mạng máy tính

Một mạng gồm n máy tính đánh số từ 1 đến n, và m kênh truyền tin 1 chiều giữa một

số cặp máy trong mạng đợc đánh số từ 1 đến m. Mạng máy tính là thông suốt, nghĩa là từ một

máy bất kỳ có thể truyền tin đến tất cả các máy còn lại hoặc là theo kênh nối trực tiếp giữa hai

máy hoặc thông qua các máy trung gian trong mạng. Một máy trong mạng đợc gọi là máy

chẵn (máy lẻ) nếu số kênh truyền tin trực tiếp từ nó đến các máy khác trong mạng là số chẵn

(số lẻ). Giả sử s và t là hai máy lẻ trong mạng. Bằng cách đảo ngợc hớng truyền tin của một

số kênh trong mạng, hãy biến đổi mạng đã cho thành mạng (không nhất thiết phải thông suốt)

mà trong đó hai máy s và t trở thành máy chẵn mà không thay đổi tính chẵn lẻ của các máy

khác.

Dữ liệu vào đợc cho trong file kiểu TEXT có tên NET.INP theo quy cách:

•

Dòng đầu tiên chứa 2 số n, m đợc ghi cách nhau bởi dấu cách (n<101);

•

Dòng thứ hai chứa 2 số nguyên dơng s, t đợc ghi cách nhau bởi dấu cách là chỉ số

của hai máy lẻ trong mạng;

•

Dòng thứ i trong số m dòng tiếp theo ghi hai số nguyên dơng u

i

, v

i

cho biết kênh

truyền tin thứ i truyền tin trực tiếp từ máy u

i

đến máy v

i

(i=1, 2, ..., m)

Kết quả ghi ra file kiểu TEXT với tên NET.OUT theo quy cách:

•

Dòng đầu ghi số lợng kênh cần thay đổi hớng truyền tin q;

•

Mỗi dòng trong số q dòng tiếp theo ghi chỉ số của kênh cần đảo ngợc hớng truyền

tin.

Ví dụ:

NET.INP

NET.OUT

6

3

9

1

1

1

7

6

2

2

4

1

5

5

5

3

6

Đề thi tin học trẻ không chuyên tq lần thứ IV-1998

Khối A - Thời gian: 120 phút