Bài toán về sự tương thích
Nguyễn Duy Khương
Có rất nhiều bài toán cần kiểm tra hoặc buộc phải kiểm tra tính giống nhau của hai thành
phần nào đó với yêu cầu tốc độ cao. Muốn 'ăn' hết test bạn cần phải có một thuật giải tốt.
Tôi xin nêu ra một cách làm tương đối hay như sau:
Trước tiên, ta phát biểu dạng tổng quát của bài toán:
Cho hai đối tương A, B (là các đồ thị, dãy số...). Hai phần tử A, B gọi là tương thích nếu
A, B cùng thoả mãn tính chất nào đó. Bài toán yêu cầu kiểm tra sự tương thích giữa hai đối
tương A, B.
Thuật giải: Xây dựng một quy tắc mã hoá thoả mãn: Tất cả các đối tượng có cùng tính chất
thì kết quả mã hoá phải giống nhau.
Xét các ví dụ:
Bài 1:
Cho hai cây A, B gồm N đỉnh (1 ≤ N ≤ 1000), gốc R1, R2. A, B gọi là tương đương nếu
chỉ cần thay đổi nhãn các đỉnh của B thì thu được A.
Yêu cầu: Hãy xác định A, B có tương đương không?
Input: TREE.IN
- Dòng đầu ghi N.
- Dòng hai ghi R1 là gốc cây A.
- N - 1 dòng tiếp mô tả các cạnh của cây A.
- Dòng tiếp theo ghi R2 là gốc của B.
- N - 1 dòng tiếp mô tả các cạnh của cây A.
Ouput: TREE.OUT
- Dòng đầu ghi là YES nếu tương đương, NO nếu không.
- Dòng thứ hai gồm N số, số thứ I là nhãn nút của cây B tương ứng với nút I của A.
Nhận xét:
- Theo như đề bài hai gốc sẽ giữ cùng nhãn.
- Như vậy ta sẽ phải sắp xếp các nút con theo một trật tự để tương đương. Bạn có thể duyệt
đến khoảng 100, nhưng > 1000 một thuật toán tối ưu hơn.
Thuật giải: Xây dựng quy tắc mã hoá một cây sau:
- Bắt đầu từ nút gốc. Ta xây dựng đệ quy như sau: Tại mỗi nút, số đầu tiên của dãy mã hoá

Last := p;
End;
Procedure Readlist;
Var i, x, y : Integer;
Begin
Assign (Fi, Tfi); Reset (Fi);
Readln (Fi, N);
Readln (Fi, R1);
For i := 1 to N - 1 do
Begin
Readln (Fi, x, y);
Push (x, Q1[y]);
Push (y, Q1[x]);
End;
Readln (Fi, R2);
For i := 1 to N - 1 do
Begin
Readln (Fi, x, y);
Push (x, Q2[y]);
Push (y, Q2[x]);
End;
Close (Fi);
End;
Procedure MakeCode (Root : Integer;
Var Q : Arr1p; Var Son : Arr1i; Var Tree : Pnode);
Procedure InitNumSon (x : Integer);
Var p : Pnode;
Begin
Visit[x] := 1;
p := Q[x];

Procedure Sort (l, r : Integer);
Var i, j : Integer;
tr : Pnode;
Begin
If l >= r Then Exit;
i := l + Random (r - l + 1);
tr := Code[1, Order[i]];
i := l;
j := r;
Repeat
While Kind (Code[1, Order[i]], tr) = 1 do i := i + 1;
While Kind (Code[1, Order[j]], tr) = 2 do j := j - 1;
If i <= j Then
Begin
Swapi (Order[i], Order[j]);
i := i + 1;
j := j - 1;
End;
Until i > j;
Sort (i, r);
Sort (l, j);
End;
Procedure BuildCode (x : Integer);
Var p : Pnode; i, All : Integer;
Begin
All := 0;
Visit[x] := 1;
p := Q[x];
While p <> Nil do
Begin

Function Check (R1, R2 : Pnode) : Boolean;
Var i : Integer;
Begin
Check := False;
For i := 1 to N do
Begin
If NSon1[R1^.x] <> Nson2[R2^.x] Then Exit;
R1 := R1^.Next;
R2 := R2^.Next;
End;
Check := True;
End;
Procedure Print;
Var i : Integer; p1, p2 : Pnode;
Begin
Assign (Fo, Tfo); Rewrite (Fo);
If Check (Tr1, Tr2) Then
Begin
Writeln (Fo, 'YES');
p1 := Tr1;
p2 := Tr2;
For i := 1 to N do
Begin
Order[p1^.x] := p2^.x;
p1 := p1^.Next;
p2 := p2^.Next;
End;
For i := 1 to N do
Write (Fo, Order[i], ' ');
Writeln (Fo);