Nguồn đề bài: http://vn.spoj.com/problems/C11BC2/
1. Đề bài C11BC2 spoj
Một ngày đẹp trời nọ, trên vương quốc của các Coders 2011, bỗng xuất hiện 1 lão phù thủy độc ác, lão phù thủy sirDat_LS đã có âm mưu thôn tính đất nước của đức vua vodanh9x. Lão phù thủy này rất yêu con gái của đức vua là Rose và đã bắt Rose về nơi ở của lão ta.
Đức vua vodanh9x liền tìm hiệp sĩ Robin và sẽ hứa gả con gái cho Robin nếu chàng cứu được công chúa Rose trở về. Lão phù thủy sirDat_LS độc ác với khuôn mặt rất ghê tởm khiến công chúa mỗi khi nhìn thấy hắn thì công chúa lại ngất đi.
Và rồi, chàng Robin của chúng ta đã tìm được đến nơi ở của lão phù thủy. Nơi ở của lão là 1 mê cung có N phòng, và N phòng này liên thông với nhau và có đúng N-1 đường đi (coi mỗi đường đi là 1 cạnh).
Nhưng khó khăn thay, lão phù thủy đã đánh số mỗi đường đi là 1 hoặc 2. Nếu chàng Robin muốn đến cứu công chúa, thì từ nơi xuất phát đến nơi có công chúa phải có ít nhất một đường đi được đánh số 2, nếu không chàng Robin sẽ chết.
Yêu cầu: Cho m truy vấn (m <= 10^5) mỗi truy vấn có dạng (x,y), trong đó x là nơi xuất phát của Robin và y là nơi nhốt công chúa. Xác định đường đi ngắn nhất từ x đến y có cạnh co trọng số 2 hay không.
Input
Dòng đầu là số nguyên N (N <= 10^4) – số đỉnh của đồ thị và M – số truy vấn.
Từ dòng 2 đến dòng N: dòng thứ i chứa 2 số nguyên dương x (x < i) và k (k <= 2) nghĩa là có cạnh nối giữa i và x và được đánh số là k.
M dòng sau: mỗi dòng chứa 2 số x và y (Biểu thị cho truy vấn (x,y)).
Output
Với mỗi truy vấn, xuất ra “YES” nếu tồn tại đường đi có ít nhất 1 cạnh có trọng số 2, ngược lại xuất ra “NO”.
Example
Input:
6 7
1 1
1 2
3 1
1 2
5 2
1 3
5 1
2 1
2 1
1 2
2 4
1 2
Output:
YES
YES
NO
NO
NO
YES
NO
2. Thuật Toán C11BC2 spoj
a. Nhận Xét
Robin đi từ x đến y có đi qua cạnh số 2. Tức là nếu không cho RoBin đi qua cạnh số 2 thì Robin không thể đi đến y được (vì đề bài cho có N-1 cạnh). Như vậy bài toán được đưa về mô hình kiểm tra liên thông.
b. Hướng dẫn
– chỉ đọc các cạnh 1 vào đồ thị, còn các cạnh 2 ta sẽ bỏ.
– Xây dựng mảng DD[i] là chỉ số vùng liên thông của đỉnh i. Xây dựng mảng này bằng thuật toán BFS hoặc DFS.
– Trả lời các truy vấn: Nếu DD[x]<>DD[y] thì kết quả là YES (bởi vì khi ta bỏ cạnh 2 ra, mà ko thể đi từ x đến y thì dễ dàng suy ra đồ thị ban đầu nếu đi từ x đến y sẽ đi qua cạnh 2). Ngược lại là NO.
3. Code tham khảo bài C11BC2 spoj
const fi='';
nmax=10000;
type data=longint;
var
f:text;
n,m:data;
head:array[0..nmax+1] of word;
canhx,canhy,adj:array[1..nmax*2] of word;
spt:data;
DD:array[0..nmax+1] of data;
count:data;
procedure dfs(u:data);
var v:data;
begin
dd[u]:=count;
for v:=head[u]+1 to head[u+1] do
if dd[adj[v]]=0 then
dfs(adj[v]);
end;
procedure docfile;
var i,j,x,k:data;
begin
readln(f,n,m);
spt:=0;
for i:=2 to n do
begin
readln(f,j,k);
if k=1 then
begin
inc(head[i]);
inc(head[j]);
inc(spt);
canhx[spt]:=i;
canhy[spt]:=j;
inc(spt);
canhx[spt]:=j;
canhy[spt]:=i;
end;
end;
head[0]:=0;
head[n+1]:=spt;
for i:=1 to n do
head[i]:=head[i-1]+head[i];
for i:=1 to spt do
begin
adj[head[canhx[i]]]:=canhy[i];
dec(head[canhx[i]]);
end;
end;
procedure xuli;
var i,j,x,y:data;
begin
for i:=0 to n do
dd[i]:=0;
count:=0;
for i:=1 to n do
if dd[i]=0 then
begin
inc(count);
dfs(i);
end;
for i:=1 to m do
begin
readln(f,x,y);
if dd[x]<>dd[y] then
writeln('YES')
else
writeln('NO');
end;
end;
begin
assign(f,fi); reset(f);
docfile;
xuli;
close(f);
end.
