BCBIN spoj PTIT - Các thùng nước

Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCBIN/

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

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.

BCBIN spoj PTIT – Các thùng nước