Cây trị sát là một cấu trúc dữ liệu hiệu quả để giải quyết bài toán về các điểm bắt buộc trong đồ thị có hướng.
Định nghĩa, Định lý và Quy ước
- Giả sử có một "đỉnh nguồn" \(s\) làm điểm xuất phát.
- Giả sử tất cả các đỉnh được đánh số thứ tự theo thứ tự duyệt DFS của chúng.
- Định nghĩa \(u\) "trị sát" \(v\) có nghĩa là nếu muốn đi qua \(v\), thì phải đi qua \(u\). Khi đó gọi \(u\) là "điểm trị sát" của \(v\).
- Cây được tạo từ các mối quan hệ trị sát gọi là cây trị sát.
- Nhiều định lý... (sẽ bổ sung sau)
Xây dựng cây trị sát cho DAG
Đối với cây ngoại hướng (out-tree), cây trị sát rõ ràng là chính nó.
Chúng ta có thể bắt đầu từ đỉnh nguồn của DAG và duyệt theo thứ tự tôpô. Khi đến một đỉnh, điểm trị sát gần nhất chắc chắn là LCA (Lowest Common Ancestor) của tất cả các đỉnh đầu vào của nó (để đến được \(u\), phải đi qua các đỉnh đầu tiên).
Dựa trên điều này, chúng ta có thể xây dựng cây trị sát cho DAG.
Bài toán liên quan: P2597 [ZJOI2012]Thảm họa ； CF757F Team Rocket Tái xuất
Mã nguồn quan trọng:
inline void duyetTopo() {
queue[++cuoi] = s;
while (dau < cuoi) {
int hienTai = queue[++dau];
int lca = 0;//Lưu ý!!
for (register unsigned int i = 0; i < danhSachKe[hienTai].size(); ++i) {
int den = danhSachKe[hienTai][i];
if (!lca) lca = den;
else lca = timLCA(lca, den);//Lưu ý!! : den
}
cha[hienTai][0] = lca;
for (register int i = 1; i <= 20; ++i)
cha[hienTai][i] = cha[cha[hienTai][i - 1]][i - 1];
for (register unsigned int i = 0; i < danhSachRa[hienTai].size(); ++i) {
int den = danhSachRa[hienTai][i];
--bacDen[den];
if (!bacDen[den]) queue[++cuoi] = den;
}
doSau[hienTai] = doSau[cha[hienTai][0]] + 1;
}
}
Xây dựng cây trị sát cho đồ thị có hướng thông thường
Một số định nghĩa và định lý khác
- Nếu có đường đi \(u -> ... -> v\), và ngoài \(u, v\), các đỉnh còn lại trên đường đi đều có \(dfn\) lớn hơn \(dfn[v]\), thì gọi \(u\) có thứ tự DFS nhỏ nhất là "điểm bán trị sát" của \(v\), ký hiệu là \(u = sdom[v]\).
- \(sdom[u]\) chắc chắn là tổ tiên của \(u\), ngoại trừ \(sdom[1]=0\).
Chứng minh: Ít nhất cha của \(u\) trên cây DFS có thể được coi là \(sdom[u]\), vì vậy các đỉnh trong cây con không thể; nếu \(sdom[u]\) ở trên các cây khác, thì ít nhất có thể tìm thấy một đường đi \(anc -> sdom[u] -> u\) trên cây, trong đó \(anc\) (tổ tiên của \(u\)) sẽ là \(sdom[u]\).
- Giữ lại các cạnh cây, xóa các cạnh không phải là cây, nối tất cả các \(sdom[cur] -> cur\), rõ ràng sẽ tạo thành một DAG, và mối quan hệ trị sát không đổi.
Chứng minh: Không thể chứng minh
Chứng minh trực quan: Chúng ta nhìn từ góc độ cây DFS là chính. Rõ ràng dưới \(sdom[cur]\) sẽ không xuất hiện điểm trị sát, vì ít nhất có hai đường dẫn đến \(cur\): đường đi trên cây và đường đi \(sdom[cur] -> cur\). Vì vậy, các cạnh không phải cây từ các đỉnh dưới \(sdom[cur]\) đến \(cur\) đều có thể xóa. Còn nếu có cạnh từ trên \(sdom[cur]\) đến \(cur\), tại sao \(sdom[cur]\) không phải là tổ tiên đó?
Phương pháp xây dựng
Cần xây dựng điểm bán trị sát cho tất cả các đỉnh, sau đó xóa các cạnh của đồ thị gốc, nối từ điểm bán trị sát đến đỉnh đó, chuyển hóa thành bài toán trên DAG.
Làm thế nào để xây dựng điểm bán trị sát? Chúng ta duyệt theo thứ tự giảm dần của số đỉnh, với mỗi đỉnh tìm các cạnh ngược. Đầu tiên, với đỉnh hiện tại \(v\), nếu tồn tại \(u -> v\) và \(u < v\), thì có thể dùng \(u\) để cập nhật \(sdom[v]\); nếu \(u -> v\) và \(u > v\), thì \(u\) đã được duyệt trước đó, theo định nghĩa chúng tadi chuyển lên trên dọc theo chuỗi từ \(u\) đến nguồn đã duyệt, sử dụng các \(sdom\) trên đường để cập nhật \(sdom[v]\). Quá trình này có thể được tối ưu bằng cấu trúc dữ liệu tập hợp hợp nhất có trọng số cạnh.
Mã nguồn quan trọng:
int sdom[N];
int cha[N], mn[N];
int tim(int cur) {
if (cha[cur] == cur) return cur;//Lưu ý!!!!!!!!!!!
int chaCur = cha[cur];
int toCung = tim(cha[cur]);
MIN(mn[cur], mn[chaCur]);//Lưu ý!!!!
cha[cur] = toCung;
return toCung;
}
inline void tinhSdom() {
for (register int i = 1; i <= n; ++i) cha[i] = mn[i] = sdom[i] = i;
for (register int i = n; i > 1; --i) {
int kq = n;
for (register unsigned int j = 0; j < danhSachNguoc[i].size(); ++j) {
int den = danhSachNguoc[i][j];
if (den < i) MIN(kq, den);
else tim(den), MIN(kq, mn[den]);//Lưu ý!!!!
}
sdom[i] = kq; cha[i] = chaDfs[i];
MIN(mn[i], kq);
}
sdom[1] = 0;
}
Sau đó xây dựng DAG và chạy thuật toán cây trị sát.
Mẫu
//P5180
int dfn[N], dcnt, mp[N], s;
int chaDfs[N];
void dfsKhoiTao(int cur) {
dfn[cur] = ++dcnt;
mp[dcnt] = cur;
for (register int i = dau[cur]; i; i = e[i].nxt) {
int den = e[i].to;
if (!dfn[den]) dfsKhoiTao(den), chaDfs[dfn[den]] = dfn[cur];
}
}
int sdom[N];
int cha[N], mn[N];
int tim(int cur) {
if (cha[cur] == cur) return cur;//Lưu ý!!!!!!!!!!!
int chaCur = cha[cur];
int toCung = tim(cha[cur]);
MIN(mn[cur], mn[chaCur]);//Lưu ý!!!!
cha[cur] = toCung;
return toCung;
}
inline void tinhSdom() {
for (register int i = 1; i <= n; ++i) cha[i] = mn[i] = sdom[i] = i;
for (register int i = n; i > 1; --i) {
int kq = n;
for (register unsigned int j = 0; j < danhSachNguoc[i].size(); ++j) {
int den = danhSachNguoc[i][j];
if (!dfn[den]) continue;
if (den < i) MIN(kq, den);
else tim(den), MIN(kq, mn[den]);//Lưu ý!!!!
}
sdom[i] = kq; cha[i] = chaDfs[i];
MIN(mn[i], kq);
}
sdom[1] = 0;
}
int d[N];
int queue[N], dau, cuoi;
int cha[N][21], doSau[N];
inline int timLCA(int u, int v) {
if (doSau[u] < doSau[v]) doiCho(u, v);
for (register int i = 20; ~i; --i)
if (doSau[cha[u][i]] >= doSau[v]) u = cha[u][i];
if (u == v) return u;
for (register int i = 20; ~i; --i)
if (cha[u][i] != cha[v][i]) u = cha[u][i], v = cha[v][i];
return cha[u][0];
}
inline void duyetTopo() {
queue[++cuoi] = s;
doSau[0] = -1;
while (dau < cuoi) {
int cur = queue[++dau], lca = 0;
for (register unsigned int i = 0; i < danhSachNguoc[cur].size(); ++i) {
int den = danhSachNguoc[cur][i];
if (!lca) lca = den;
else lca = timLCA(lca, den);
}
cha[cur][0] = lca; doSau[cur] = doSau[lca] + 1;//Lưu ý!!!!
for (register int i = 1; i <= 20; ++i)
cha[cur][i] = cha[cha[cur][i - 1]][i - 1];
for (register int i = dau[cur]; i; i = e[i].nxt) {
int den = e[i].to;
--d[den];
if (!d[den]) queue[++cuoi] = den;
}
}
}
int kichThuoc[N];
void dfsKichThuoc(int cur) {
kichThuoc[cur] = 1;
for (register int i= dau[cur]; i; i = e[i].nxt) {
int den = e[i].to;
dfsKichThuoc(den);
kichThuoc[cur] += kichThuoc[den];
}
}
inline lamViec() {
memset(dau, 0, sizeof(dau));
canh = 0;
for (register int i = 2; i <= n; ++i) themCanh(cha[i][0], i);
dfsKichThuoc(s);
}
int kq[N];
int main() {
nhap(n), nhap(m);
for (register int i = 1; i <= m; ++i) {
int u, v; nhap(u), nhap(v);
themCanh(u, v);
}
dfsKhoiTao(1); s = dfn[1];
for (register int i = 1; i <= n; ++i) {
for (register int j = dau[i]; j; j = e[j].nxt) {
int den = e[j].to;
themCanhNguoc(dfn[den], dfn[i]);
}
}
memset(dau, 0, sizeof(dau));
canh = 0;
for (register int i = 1; i <= n; ++i) {
for (register unsigned int j = 0; j < danhSachNguoc[i].size(); ++j) {
int den = danhSachNguoc[i][j];
themCanh(den, i);
}
}
tinhSdom();
memset(dau, 0, sizeof(dau));
canh = 0;
for (register int i = 1; i <= n; ++i)
danhSachNguoc[i].clear();
for (register int i = 2; i <= n; ++i)
themCanh(sdom[i], i), ++d[i], themCanhNguoc(i, sdom[i]),
themCanh(chaDfs[i], i), ++d[i], themCanhNguoc(i, chaDfs[i]);//Lưu意!!!!!!
duyetTopo();
lamViec();
for (register int i = 1; i <= n; ++i)
kq[mp[i]] = kichThuoc[i];
for (register int i = 1; i <= n; ++i)
printf("%d ", kq[i]);//Lưu意!!!!!!!!!!!!!!
puts("");
return 0;
}
Phương pháp ghi nhớ
Tôi kém cỏi nên chỉ có thể học thuộc lòng
Với DAG thì rất dễ hiểu, chỉ cần tính LCA của tất cả các đỉnh tiền nhiệm (đỉnh đầu vào) là được.
Với đồ thị có hướng, cần nhớ:
- Định nghĩa điểm bán trị sát của một đỉnh: nếu
sdom[v]=u, thì tồn tại một đường đi từ \(u\) đến \(v\), trong đó các đỉnh còn lại trên đường đi có \(dfn\) đều lớn hơn \(v\). Nếu có nhiều \(u\) như vậy, chọn \(u\) có \(dfn\) nhỏ nhất. - Kết luận: Chỉ giữ lại các cạnh cây DFS và các cạnh \(sdom_x \to x\) sẽ tạo thành DAG, và cây trị sát của DAG này chính là cây trị sát của đồ thị có hướng ban đầu.
- Phương pháp xây dựng: Duyệt theo thứ tự giảm dần của \(dfn\), với mỗi đỉnh, duyệt các đỉnh tiền nhiệm (cạnh vào). Nếu tiền nhiệm có \(dfn\) nhỏ hơn nó, cập nhật trực tiếp; ngược lại, sử dụng tất cả các tổ tiên của tiền nhiệm (có thể đảm bảo các đỉnh trên chuỗi có \(dfn\) lớn hơn \(dfn\) của đỉnh hiện tại) để cập nhật \(sdom\) của đỉnh hiện tại. Cần hỗ trợ thêm động, tra cứu giá trị trên chuỗi, sử dụng tập hợp hợp nhất có trọng số cạnh.