¶ Cây DFS (Depth-First Search Tree) và ứng dụng
Tác giả:
- Nguyễn Châu Khanh - THPT Chuyên Hùng Vương - Phú Thọ
- Bùi Minh Hoạt - THPT Chuyên Hùng Vương - Phú Thọ
- Trần Thế Hưng - THPT Chuyên Biên Hòa - Hà Nam
Reviewer:
- Đỗ Đình Đắc - Đại học Bách Khoa Hà Nội
¶ Mở đầu
- Bài viết này sẽ giúp bạn tìm hiểu về cây (Depth First Search Tree – DFS Tree). Cây là một ứng dụng quan trọng có được từ kỹ thuật duyệt đồ thị ưu tiên chiều sâu, giúp giải các bài toán tìm khớp cầu và thành phần liên thông mạnh.
¶ Cây duyệt chiều sâu DFS (cây DFS)
- Trong quá trình , với mỗi đỉnh ta có đỉnh là số hiệu của đỉnh mà từ đỉnh đó thủ tục gọi đệ quy đến . Xây dựng đồ thị con với các cạnh là ta có được một cây. Cây này được gọi là cây DFS.
- Các cạnh thuộc cây được gọi là các “cạnh nét liền”.
- Các cạnh còn lại không thuộc cây được gọi là các “cạnh nét đứt".
-
Trong đồ thị có hướng, xét các cung được thăm và không được thăm bởi , ta có loại cung sau:
- Cung của cây (Tree edge): là các cung thuộc cây được định hướng theo chiều từ cha đến con. (ví dụ cạnh thuộc cây mà được thăm trước hay là cha của thì ta có cung là cung của cây ). Các cung của cây được đánh dấu là các cạnh màu đen trong hình bên dưới
- Cung xuôi (Forward edge): là các cung không thuộc cây và có dạng trong đó là tổ tiên của trong cây . Các cung xuôi được đánh dấu là các cạnh màu xanh lá trong hình bên dưới
- Cung ngược (Back edge): là các cung không thuộc cây và có dạng trong đó là tổ tiên của trong cây . Các cung ngược được đánh dấu là các cạnh màu đỏ trong hình bên dưới
- Cung chéo (Cross edge): là các cung không thuộc cây có dạng trong đó và thuộc hai nhánh khác nhau của cùng một cây . Các cung chéo được đánh dấu là các cạnh màu xanh dương trong hình bên dưới
-
Trong đồ thị vô hướng:
- Không tồn tại cung chéo. Vì khi đỉnh được duyệt trong hàm ta sẽ duyệt tất cả các đỉnh kề mà chưa được thăm. Như vậy nếu tồn tại một cung chéo chứng tỏ khi duyệt đến đỉnh hoặc đỉnh ta đã không duyệt cạnh .
- Vì các cạnh trên đồ thị vô hướng không được định chiều nên không thể định nghĩa loại cung xuôi và cung ngược như ở đồ thị có hướng. Do đó, ở đồ thị vô hướng, cung xuôi và cung ngược sẽ được định nghĩa như sau:
- Cung xuôi (Forward edge): là các cung thuộc cây . Hay còn có cách gọi khác là "cạnh nét liền" hoặc "cung của cây ".
- Cung ngược (Back edge): là các cung không thuộc cây . Hay còn có cách gọi khác là "cạnh nét đứt".
- Như vậy trên đồ thị vô hướng lúc này chỉ còn loại cung là cung ngược và cung xuôi (cung của cây ).
Một số mảng quan trọng trong cây DFS :
- Mảng []: cho biết thứ tự duyệt của các đỉnh (thứ tự mà mỗi đỉnh bắt đầu duyệt).
- Mảng []: Với mỗi đỉnh , cho biết thứ tự (giá trị ) nhỏ nhất có thể đi đến được từ bằng cách đi xuôi xuống theo các cạnh nét liền (các cung trên cây ) và kết thúc đi ngược lên không quá lần theo cạnh nét đứt. Ngoài ra ta cũng có thể hiểu ý nghĩa của là thứ tự thăm của đỉnh có thứ tự thăm sớm nhất nằm trong cây con gốc hoặc kề cạnh với đỉnh bất kì nằm trong cây con gốc .
- Mảng []: cho biết thời điểm kết thúc duyệt của mỗi đỉnh cũng là thời điểm duyệt xong của đỉnh đó .
Nhận xét : Các đỉnh có thứ tự thăm nằm trong khoảng từ đến chính là các đỉnh nằm trong cây con gốc trong cây .
Cách tính mảng low[], num[], tail[] :
- Ý tưởng chính : Mảng ta có thể tính dễ dàng bằng cách xác định thời điểm duyệt tới và thời điểm duyệt xong của các đỉnh. Với mảng ta có:
- Trước hết, với đỉnh bất kì có thể tự đi tới chính nó nên ta gán .
- Từ có thể đến các đỉnh kề bằng cạnh nét đứt nên ta có với là một cạnh nét đứt.
- Ngược lại, nếu là một cạnh nét liền và không phải cha ta có do từ ta có thể đi xuống sau đó đi theo con đường đã xác định ở đỉnh để tới đỉnh có thứ tự thăm là .
- Chú ý: Giá trị thực sự của được xác định khi duyệt tới đỉnh còn giá trị thực sự của chỉ được xác định khi đã duyệt xong đỉnh . Thời điểm duyệt tới của một đỉnh luôn diễn ra trước thời điểm duyệt tới của các đỉnh trong cây con gốc của cây , thời điểm duyệt xong của đỉnh luôn diễn ra sau thời điểm duyệt xong của các đỉnh trong cây con gốc .
- Cách thực hiện :
- Đầu tiên ta sẽ bắt đầu duyệt từ đỉnh gốc. Khi duyệt tới đỉnh ta sẽ cập nhật thời điểm duyệt tới. Lúc này thứ tự duyệt DFS. Ta sẽ duyệt tất cả các con trong gốc .
- Trường hợp 1: Nếu đỉnh chưa được thăm thì sau khi hoàn thành của thì ta sẽ cập nhật lại giá trị của :
- Trường hợp 2: Nếu đỉnh đã được thăm, thì ta sẽ cập nhật lại giá trị cho :
- Ở trường hợp này ta không thể cập nhật được. Vì khi ta thăm đến đỉnh mà đỉnh đã được thăm thì tức là là một cạnh nét đứt, do đó khi đi từ tới ta đã sử dụng cạnh nét đứt nên không thể tiếp tục di chuyển nữa (theo định nghĩa của mảng ) suy ra ta chỉ cập nhật .
- Chú ý : Nếu v là cha trực tiếp của u thì ta bỏ qua không xét đến.
- Khi đã duyệt xong đỉnh và các nút trong cây con gốc ta sẽ tiến hành cập nhật giá trị thời gian duyệt DFS hiện tại.
- Cài đặt :
int timeDfs = 0; // Thứ tự duyệt DFS
void dfs(int u, int pre) {
num[u] = low[u] = ++timeDfs;
for (int v : g[u]){
if (v == pre) continue;
if (!num[v]) {
dfs(v, u);
low[u] = min(low[u], low[v]);
}
else low[u] = min(low[u], num[v]);
}
tail[u] = timeDfs;
}
-
Ví dụ minh họa :
-
Mô tả quá trình :
¶ Ứng dụng cây DFS trong bài toán tìm khớp, cầu
¶ Định nghĩa
-
Trong đồ thị vô hướng, một đỉnh được gọi là đỉnh khớp nếu như loại bỏ đỉnh này và các cạnh liên thuộc với nó ra khỏi đồ thị thì số thành phần liên thông của đồ thị tăng lên.
-
Trong đồ thị vô hướng, một cạnh được gọi là cạnh cầu nếu như loại bỏ cạnh này ra khỏi đồ thị thì số thành phần liên thông của đồ thị tăng lên.
¶ Bài toán 1
GRAPH_ - Tìm khớp và cầu (Cơ bản)
¶ Đề bài
Xét đơn đồ thị vô hướng có đỉnh và cạnh. Người ta định nghĩa một đỉnh gọi là khớp nếu như xoá đỉnh đó sẽ làm tăng số thành phần liên thông của đồ thị. Tương tự như vậy, một cạnh được gọi là cầu nếu xoá cạnh đó sẽ làm tăng số thành phần liên thông của đồ thị.
Vấn đề đặt ra là cần phải đếm tất cả các khớp và cầu của đồ thị .
Input
- Dòng đầu: chứa hai số tự nhiên .
- dòng sau mỗi dòng chứa một cặp số khác , mô tả một cạnh của .
Output
- Gồm một dòng duy nhất ghi hai số, số thứ nhất là số khớp, số thứ hai là số cầu của .
Example
Input
10 12
1 10
10 2
10 3
2 4
4 5
5 2
3 6
6 7
7 3
7 8
8 9
9 7
Output
4 3
Note
- Các cạnh màu đỏ là cạnh cầu.
- Các đỉnh màu xanh lá là đỉnh khớp.
¶ Phân tích
¶ Tìm cạnh cầu
- Dễ thấy rằng cạnh cầu của đồ thị không thể là cạnh nét đứt vì việc bỏ đi cạnh nét đứt sẽ không ảnh hưởng đến tính liên thông giữa các đỉnh của đồ thị. Do vậy cạnh cầu chỉ có thể là cạnh nét liền.
- Ta sẽ xét riêng từng thành phần liên thông của đồ thị. Xét vùng liên thông như sau:
-
Xét cây con gốc trong cây của có là cha trực tiếp của . Gọi tập hợp các đỉnh thuộc cây con gốc là , tập hợp các đỉnh không thuộc cây con gốc là . Khi xoá đi cạnh thì giữa đỉnh bất kì thuộc cùng tập hợp vẫn có thể đến với nhau bằng các cạnh nét liền. Một đỉnh thuộc với một đỉnh thuộc muốn đi đến với nhau bằng các cạnh nét liền thì đều phải thông qua cạnh .
- Ví dụ minh họa: Xét cạnh nét liền với đỉnh là con trực tiếp của đỉnh trên cây . Tập đỉnh là các đỉnh được đánh dấu màu hồng. Tập đỉnh là các đỉnh được đánh dấu màu vàng. Đỉnh thuộc tập muốn đi đến đỉnh thuộc tập bằng các cạnh nét liền thì đều phải thông qua cạnh .
-
Giả sử không có cạnh nét đứt nào nối giữa đỉnh thuộc với đỉnh thuộc thì khi xoá cạnh , sẽ tách ra thành vùng liên thông và . Ngược lại nếu tồn tại cạnh nét đứt nối giữa đỉnh thuộc và đỉnh thuộc đồ thị vẫn liên thông . Do đó ta chỉ cần xét xem có tồn tại cạnh nét đứt nối giữa và hay không để kết luận có phải cầu không?
-
Ta có từ có thể đi đến một đỉnh nào đó có bằng cách đi theo các cung của cây và đi qua không quá cạnh nét đứt và có thứ tự thăm sớm nhất khi . Nếu nằm trong thì phải là tổ tiên của cũng đồng nghĩa với việc hay (vì đồ thị không có cung chéo), nghĩa là tồn tại cạnh nét đứt nối giữa đỉnh thuộc với đỉnh thuộc (vì nếu chỉ đi bằng các cung của cây thì không thể tới một tổ tiên của nó).
-
Do đó nếu chắc chắn đỉnh thuộc cây con gốc hay thuộc tập hợp khi đó không tồn tại cạnh nét đứt nối giữa đỉnh thuộc với đỉnh thuộc . Tuy nhiên, ta dễ dàng nhận thấy vì đỉnh luôn tới được chính nó.
-
- Kết luận: Nếu thì là một cạnh cầu trong đồ thị.
¶ Tìm đỉnh khớp
-
Ta sẽ xét riêng từng thành phần liên thông của đồ thị. Xét vùng liên thông như sau:
-
Xét cây con gốc trong cây của , nếu mọi nhánh con của đều có cung ngược lên tới tổ tiên của (, với là tất cả các con trực tiếp của trên cây ) thì đỉnh không thể là đỉnh khớp. Bởi trong đồ thị ban đầu, nếu ta loại bỏ đỉnh đi thì từ mỗi đỉnh bất kỳ thuộc nhánh con vẫn có thể đi lên một tổ tiên của , rồi đi sang nhánh con khác hoặc đi sang tất cả những đỉnh còn lại của cây nên số thành phần liên thông của đồ thị không thay đổi.
- Ví dụ minh họa: Xét đỉnh không phải là đỉnh khớp vì cả nhánh con của nó là cây con gốc và cây con gốc trong cây đều có cung ngược lên tới đỉnh là tổ tiên của đỉnh .
-
Nếu không phải là đỉnh gốc của cây , và tồn tại ít nhất một nhánh con trong cây con gốc không có cung ngược lên một tổ tiên của (, với là một con trực tiếp bất kì của trên cây ) thì đỉnh là đỉnh khớp. Bởi khi đó, tất cả những cung xuất phát từ nhánh con đó chỉ có thể đi tới những đỉnh thuộc cây con gốc mà thôi, trên đồ thị ban đầu, không tồn tại cạnh nối từ những đỉnh thuộc nhánh con đó tới một tổ tiên của . Vậy nên từ một đỉnh bất kì thuộc nhánh con đó muốn đi lên một tổ tiên của thì bắt buộc phải đi qua nên việc loại bỏ đỉnh ra khỏi đồ thị sẽ làm tăng số thành phần liên thông của đồ thị.
- Ví dụ minh họa: Xét đỉnh là đỉnh khớp vì tồn tại nhánh con của nó là cây con gốc không có cung ngược lên tới tổ tiên của đỉnh .
-
Nếu là đỉnh gốc của cây , thì là đỉnh khớp khi và chỉ khi có ít nhất nhánh con. Vì đồ thị không có cung chéo nên khi có nhánh con thì đường đi giữa hai đỉnh thuộc hai nhánh con đó bắt buộc phải đi qua . Việc loại bỏ đỉnh ra khỏi đồ thị sẽ làm tăng số thành phần liên thông của đồ thị.
- Ví dụ minh họa: Xét đỉnh là đỉnh khớp vì đỉnh là đỉnh gốc của cây và có tới nhánh con.
-
-
Kết luận: Đỉnh là đỉnh khớp khi:
- Đỉnh không phải là gốc của cây và (với là một con trực tiếp bất kì của trong cây ).
Hoặc
- Đỉnh là gốc của cây và có ít nhất con trực tiếp trong cây .
¶ Cài đặt
Cấu trúc dữ liệu:
- Hằng số
maxN = 10010 - Biến
timeDfs- Thứ tự - Biến
bridge- Số lượng cạnh cầu - Mảng
low[], num[] - Mảng
joint[]- Đánh dấu đỉnh khớp - Vector
g[]- Danh sách cạnh kề của mỗi đỉnh
#include <bits/stdc++.h>
using namespace std;
const int maxN = 10010;
int n, m;
bool joint[maxN];
int timeDfs = 0, bridge = 0;
int low[maxN], num[maxN];
vector <int> g[maxN];
void dfs(int u, int pre) {
int child = 0; // Số lượng con trực tiếp của đỉnh u trong cây DFS
num[u] = low[u] = ++timeDfs;
for (int v : g[u]) {
if (v == pre) continue;
if (!num[v]) {
dfs(v, u);
low[u] = min(low[u], low[v]);
if (low[v] == num[v]) bridge++;
child++;
if (u == pre) { // Nếu u là đỉnh gốc của cây DFS
if (child > 1) joint[u] = true;
}
else if (low[v] >= num[u]) joint[u] = true;
}
else low[u] = min(low[u], num[v]);
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; i++)
if (!num[i]) dfs(i, i);
int cntJoint = 0;
for (int i = 1; i <= n; i++) cntJoint += joint[i];
cout << cntJoint << ' ' << bridge;
}
¶ Đánh giá
- Độ phức tạp của bài toán là .
¶ Bài toán 2
¶ Đề bài
Để truy bắt tội phạm, cảnh sát xây dựng một hệ thống máy tính mới. Bản đồ khu vực bao gồm thành phố và đường nối chiều. Các thành phố được đánh số từ đến .
Cảnh sát muốn bắt các tội phạm di chuyển từ thành phố này đến thành phố khác. Các điều tra viên, theo dõi bản đồ, phải xác định vị trí thiết lập trạm gác. Hệ thống máy tính mới phải trả lời được loại truy vấn sau:
- . Đối với hai thành phố , và một đường nối giữa hai thành phố , ; hỏi tội phạm có thể di chuyển từ đến nếu đường nối này bị chặn (nghĩa là tên tội phạm không thể sử dụng con đường này) không?
- . Đối với thành phố , , ; hỏi tội phạm có thể di chuyển từ đến nếu như toàn bộ thành phố bị kiểm soát (nghĩa là tên tội phạm không thể đi vào thành phố này) không?
Input
- Dòng đầu tiên chứa số nguyên và , số thành phố và số đường nối.
- Mỗi dòng trong số dòng tiếp theo chứa số nguyên phân biệt thuộc phạm vi - cho biết nhãn của hai thành phố nối với nhau bởi một con đường. Giữa hai thành phố có nhiều nhất một đường nối.
- Dòng tiếp theo chứa số nguyên , số truy vấn được thử nghiệm trên hệ thống.
- Mỗi dòng trong dòng tiếp theo chứa hoặc số nguyên. Số đầu tiên cho biết loại truy vấn hoặc .
- Nếu loại truy vấn là , tiếp theo trên cùng dòng là số nguyên , , , với ý nghĩa như đã mô tả. khác ; , mô tả một con đường có sẵn.
- Nếu loại truy vấn là , tiếp theo trên cùng dòng là số nguyên , , với ý nghĩa như đã mô tả. , , đôi một khác nhau.
Dữ liệu được cho sao cho ban đầu luôn có cách di chuyển giữa hai thành phố bất kỳ.
Output
- Gồm dòng, mỗi dòng chứa câu trả lời cho một truy vấn. Nếu câu trả lời là khẳng định, in ra "yes". Nếu câu trả lời là phủ định, in ra "no".
Example
Input
13 15
1 2
2 3
3 5
2 4
4 6
2 6
1 4
1 7
7 8
7 9
7 10
8 11
8 12
9 12
12 13
5
1 5 13 1 2
1 6 2 1 4
1 13 6 7 8
2 13 6 7
2 13 6 8
Output
yes
yes
yes
no
yes
Note
¶ Phân tích
- Để tồn tại ít nhất một cách di chuyển từ thành phố đến thành phố thì cả thành phố và phải cùng thuộc một thành phần liên thông.
¶ Truy vấn 1
-
Dễ thấy rằng, nếu đường nối giữa thành phố không phải là cạnh cầu thì việc loại bỏ nó đi sẽ không ảnh hưởng đến tính liên thông giữa thành phố và .
-
Ngược lại, nếu đường nối giữa thành phố là cạnh cầu thì ta phải kiểm tra xem thành phố và có thuộc cùng một thành phần liên thông sau khi loại bỏ cạnh hay không?
-
Mỗi khi loại bỏ một cạnh cầu của đồ thị vô hướng thì số thành phần liên thông của đồ thị sẽ tăng thêm . Nghĩa là khi ta loại bỏ cạnh cầu (với là con trực tiếp của ) thì đồ thị sẽ chia ra làm thành phần liên thông:
- Thành phần liên thông thứ nhất là tập hợp các đỉnh thuộc cây con gốc của cây .
- Thành phần liên thông thứ nhất là tập hợp các đỉnh còn lại không thuộc cây con gốc của cây .
-
Ví dụ minh họa: Loại bỏ cạnh cầu (với đỉnh là con trực tiếp của đỉnh )
-
Bây giờ, ta có thể xác định vị trí của đỉnh có nằm trong cây con gốc hay không.
- Nếu chỉ có đúng duy nhất trong đỉnh nằm trong cây con gốc thì thành phố và không thuộc cùng một thành phần liên thông sau khi loại bỏ cạnh .
- Ngược lại, nếu cả đỉnh cùng nằm trong cây con gốc hoặc cả đỉnh đều không nằm trong cây con gốc thì thành phố và đều thuộc cùng một thành phần liên thông sau khi loại bỏ cạnh .
-
Nhắc lại: Nếu thì đỉnh nằm trong cây con gốc của cây .
¶ Truy vấn 2
-
Dễ thấy rằng, nếu thành phố không phải là đỉnh khớp thì việc loại bỏ nó đi sẽ không ảnh hưởng đến tính liên thông giữa thành phố và .
-
Ngược lại, nếu thành phố là đỉnh khớp thì ta phải kiểm tra xem thành phố và có thuộc cùng một thành phần liên thông sau khi loại bỏ đỉnh và các cạnh liên thuộc với nó đi hay không?
-
Vì đồ thị không có cung chéo nên khi loại bỏ đỉnh khớp ra khỏi đồ thị thì số thành phần liên thông của đồ thị tăng thêm một lượng bằng số lượng đỉnh là con trực tiếp của trong cây sao cho không tồn tại cung ngược (cạnh nét đứt) từ một đỉnh thuộc cây con gốc trong cây nối lên tổ tiên của (đồng nghĩa với việc ). Nghĩa là khi ta loại bỏ đỉnh khớp ra khỏi đồ thị thì đồ thị sẽ chia ra làm các thành phần liên thông:
- Một số thành phân liên thông, mỗi thành phần liên thông là tập hợp các đỉnh thuộc cây con gốc với là con trực tiếp của trong cây và .
- Một thành phần liên thông là tập hợp tất cả các đỉnh còn lại (bao gồm các đỉnh là tổ tiên của của và các đỉnh thuộc các cây con gốc với là các con trực tiếp của trong cây và ).
-
Ví dụ minh họa: Loại bỏ đỉnh khớp . Đỉnh và là các con trực tiếp của đỉnh trong cây . Nhưng chỉ có cây con gốc là tách riêng ra thành thành phần liên thông riêng biệt. Còn cây con gốc thì có cung ngược nối lên đỉnh (tổ tiên của đỉnh ) nên số lượng thành phần liên thông của cả đồ thị chỉ tăng thêm .
-
Với mỗi đỉnh là con trực tiếp của trong cây và , ta kiểm tra xem nếu chỉ có đúng duy nhất trong đỉnh nằm trong cây con gốc thì thành phố và không thuộc cùng một thành phần liên thông sau khi loại bỏ đỉnh và các cạnh liên thuộc với đỉnh đi.
-
Ngược lại, với là các con trực tiếp của trong cây và , nếu cả đỉnh và cùng nằm trong cây con gốc hoặc cả đỉnh và đều không nằm trong bất cứ cây con gốc nào cả (đồng nghĩa với việc cả đỉnh sẽ cùng nằm trong thành phần liên thông còn lại) thì thành phố và đều thuộc cùng một thành phần liên thông sau khi loại bỏ đỉnh và các cạnh liên thuộc với đỉnh đi.
-
Tuy nhiên theo thuật toán trên thì với mỗi truy vấn ta sẽ phải duyệt hết tất cả các con trực tiếp của đỉnh C nên khi xử lí các truy vấn sẽ mất độ phức tạp là O(Q⋅ bậc của C). Trong trường hợp tệ nhất thì đỉnh C có thể lên đến N - 1 con trực tiếp (100000 - 1) với số lượng truy vấn Q = 300000, khiến cho thuật toán trên sẽ bị quá thời gian. Bây giờ ta cần phải cải tiến thuật toán :
-
Thay vì duyệt hết tất cả các con trực tiếp của để xác định được tổ tiên của , tổ tiên của . Ta có thể sử dụng để tìm ra tổ tiên của đỉnh (hoặc ) là con trực tiếp của đỉnh nếu (hoặc ) nằm trong cây con gốc .
Bạn có thể tìm hiểu thêm về Sparse Table và ứng dụng của nó tại đây. -
Gọi đỉnh là tổ tiên của đỉnh và là con trực tiếp của đỉnh .
-
Gọi đỉnh là tổ tiên của đỉnh và là con trực tiếp của đỉnh .
-
và thuộc cùng một thành phần liên thông sau khi loại bỏ đỉnh và các cạnh liên thuộc với đỉnh đi khi thỏa mãn một trong số các điều kiện sau:
- Nếu cả đỉnh và đều không nằm trong cây con gốc .
- Nếu (nghĩa là cả đỉnh và đều nằm trong cây con gốc ).
- Nếu không nằm trong cây con gốc và nằm trong cây con gốc sao cho (nghĩa là có tồn tại cung ngược nối từ cây con gốc lên tổ tiên của ).
- Nếu không nằm trong cây con gốc và nằm trong cây con gốc sao cho (nghĩa là có tồn tại cung ngược nối từ cây con gốc lên tổ tiên của ).
- Nếu cả đỉnh và đều nằm trong cây con gốc và và (nghĩa là cả cây con gốc và cây con gốc đều có cung ngược nối lên tổ tiên của )
-
Ngược lại, nếu không thỏa mãn tất cả các điều kiện trên thì và không thuộc cùng một thành phần liên thông sau khi loại bỏ đỉnh và các cạnh liên thuộc với đỉnh đi.
-
Lúc này, độ phức tạp để xử lí các truy vấn sẽ là .
¶ Cài đặt
Cấu trúc dữ liệu:
- Hằng số
maxN = 100010 - Biến
timeDfs- Thứ tự - Mảng
low[], num[], tail[] - Mảng
depth[]- Lưu chiều sâu của mỗi đỉnh trong cây - Mảng
p[][]- Mảng ứng dụng với là tổ tiên thứ của trong cây - Mảng
joint[]- Đánh dấu đỉnh khớp - Vector
g[]- Danh sách cạnh kề của mỗi đỉnh
#include <bits/stdc++.h>
using namespace std;
const int maxN = 100010;
int n, m, q;
int timeDfs = 0;
int low[maxN], num[maxN], tail[maxN];
int depth[maxN], p[maxN][20];
bool joint[maxN];
vector <int> g[maxN];
/* Tính mảng p */
void calP() {
p[1][0] = 1;
for (int j = 1; j <= 19; j++)
for (int i = 1; i <= n; i++)
p[i][j] = p[p[i][j - 1]][j - 1];
}
/* Tìm tổ tiên của đỉnh u là con trực tiếp của đỉnh par */
int findParent(int u, int par) {
for (int i = 19; i >= 0; i--)
if (depth[p[u][i]] > depth[par]) u = p[u][i];
return u;
}
/* Tìm khớp cầu */
void dfs(int u, int pre) {
int child = 0;
num[u] = low[u] = ++timeDfs;
for (int v : g[u]){
if (v