Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCBIN/
Nội dung bài viết
1. Đề bài BCBIN spoj
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
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
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.
Example
Input:
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
Output:
0
0
1
0
1
0
Giới hạn
- 1 ≤ N ≤ 10000
- 1 ≤ P ≤ 50000
2. Gợi ý BCBIN spoj PTIT
– Áp dụng tư tưởng Kruskal, đếm số thành phần liên thông
3. Code tham khảo BCBIN spoj PTIT
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | const fi=''; nmax=10000; type data=longint; var f:text; root:array[0..nmax+1] of data; p:data; procedure union(a,b:data); begin root[a]:=b; end; function findroot(x:data):data; begin if root[x]<>x then root[x]:=findroot(root[x]); exit(root[x]); end; procedure docfile; var i,j,u,v,tl,ur,uv:data; begin assign(f,fi); reset(f); readln(f,p); for i:=1 to nmax do root[i]:=i; for i:=1 to p do begin readln(f,u,v,tl); ur:=findroot(u); uv:=findroot(v); if tl=1 then begin if ur<>uv then union(ur,uv); end else begin if ur=uv then writeln(1) else writeln(0); end; end; close(f); end; begin docfile; end. |
Bài viết liên quan
- BCLKCOUN spoj PTIT – Đếm số ao
- Cấu trúc dữ liệu Disjoint Sets
- BCGRASS spoj PTIT – Bãi cỏ ngon nhất
- BCACM11E spoj PTIT – Phương án bắn pháo
- BCISLAND PTIT spoj – Nước biển
- P167PROE spoj PTIT – ROUND 7E – Phương trình
- PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
- PTIT016D spoj PTIT- ACM PTIT 2016 D – Biểu thức
- Spoj PTIT PTIT016C – ACM PTIT 2016 C – Chẵn lẻ
- PTIT127A spoj PTIT – Tổ chức kì thi