//
you're reading...
Bài tập huấn luyện, Chủ đề đồ thị (Graph)

Bài tập huấn luyện: Các thùng nước

[Bộ đề huấn luyện về chủ đề đồ thị]


Chuyên đề Đồ thị (Graph) – Bài 4


Đề bài


Có N thùng nước được đánh số từ 1 đến N, giữa 2 thùng bất kỳ đều có một ống nối có một van có thể khóa hoặc mở. Ở trạng thỏi ban đầu tất cả cỏc van đều đóng.

Bạn được cho một số yêu cầu, trong đó mỗi yêu cầu có 2 dạng:

  • Dạng X Y 1 cú ý nghĩa là bạn cần mở van nối giữa 2 thựng X và Y.
  • Dạng X Y 2 cú ý nghĩa là bạn cần cho biết với trạng thái các van đang mở / khóa như hiện tại thỡ 2 thựng X và Y cú thuộc cựng một nhúm bỡnh thụng nhau hay khụng? Hai thựng được coi là thuộc cùng một nhóm bỡnh thụng nhau nếu nước từ bỡnh nàycú thể chảy đến được bỡnh kia qua một số ống cú van đang mở.

Input:    BIN.INP

  • Dũng đầu tiờn ghi một số nguyên dương P là số yờu cầu.
  • Trong P dũng tiếp theo, mỗi dũng ghi ba số nguyên dương X, Y, Z với ý nghĩa cú yờu cầu loại Z với 2 thựng X và Y.

Output: BIN.OUT

Với mỗi yờu cầu dạng X Y 2 (với Z = 2) bạn cần ghi ra số 0 hoặc 1 trờn 1 dũng tựy thuộc 2 thựng X và Y khụng thuộc hoặc thuộc cựng một nhúm bỡnh.

Giới hạn:

  • 1 ≤ N ≤ 10000
  • 1 ≤ P ≤ 50000
  • Thời gian: 1 s/test
  • Bộ nhớ: 1 MB

Vớ dụ:

BIN.INP BIN.OUT
9

1 2 2

1 2 1

3 7 2

2 3 1

1 3 2

2 4 2

1 4 1

3 4 2

1 7 2

0

0

1

0

1

0

 

 

 


Hướng dẫn


[]


Chương trình


[]

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười Hai 2016
H B T N S B C
« Th11   Th1 »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

Thống kê

  • 149,393 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: