Bài toán duyệt đồ thị theo chiều sâu

Question

Nhận xét : Các đỉnh có thứ tự thăm nằm trong khoảng từ $num[u]$ đến $tail[u]$ chính là các đỉnh nằm trong cây con gốc $u$ trong cây $DFS$.

Nội dung chính Show

Ứng dụng cây DFS trong bài toán tìm khớp, cầu
Định nghĩa
Bài toán 1
Phân tích
Cài đặt
Đánh giá
Bài toán 2
Phân tích
Cài đặt
Đánh giá
Bài toán 3
Phân tích
Cài đặt
Đánh giá
Bài toán 5

Cách tính mảng low[], num[], tail[] :

Ý tưởng chính : Mảng $num[],tail[]$ ta có thể tính dễ dàng bằng cách $DFS$ 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 $low[]$ ta có:
- Trước hết, với $1$ đỉnh $u$ bất kì có thể tự đi tới chính nó nên ta gán $low[u]=num[u]$.
- Từ $u$ có thể đến các đỉnh $v$ kề $u$ bằng $1$ cạnh nét đứt nên ta có $low[u]=min(low[u],num[v])$ với $(u,v)$ là một cạnh nét đứt.
- Ngược lại, nếu $(u,v)$ là một cạnh nét liền và $v$ không phải cha $u$ ta có $low[u]=min(low[u],low[v])$ do từ $u$ ta có thể đi xuống $v$ sau đó đi theo con đường đã xác định ở đỉnh $v$ để tới đỉnh có thứ tự thăm là $low[v]$.
Chú ý: Giá trị thực sự của $num[u]$ được xác định khi duyệt tới đỉnh $u$ còn giá trị thực sự của $low[u],$ $tail[u]$ chỉ được xác định khi đã duyệt xong đỉnh $u$. Thời điểm duyệt tới của một đỉnh $u$ 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 $u$ của cây $DFS$ , thời điểm duyệt xong của đỉnh $u$ luôn diễn ra sau thời điểm duyệt xong của các đỉnh trong cây con gốc $u$.
Cách thực hiện :
- Đầu tiên ta sẽ bắt đầu duyệt $DFS$ từ đỉnh gốc. Khi duyệt tới đỉnh $u$ ta sẽ cập nhật thời điểm duyệt tới. Lúc này $low[u] = num[u] =$ thứ tự duyệt DFS. Ta sẽ duyệt tất cả các con $v$ trong gốc $u$.
- Trường hợp 1: Nếu đỉnh $v$ chưa được thăm thì sau khi hoàn thành $DFS$ của $v$ thì ta sẽ cập nhật lại giá trị của $low [u]$: $low [u] = min (low[u], low[v]);$
- Trường hợp 2: Nếu đỉnh $v$ đã được thăm, thì ta sẽ cập nhật lại giá trị cho $low[u]$: $low [u] = min (low [u], num[v]);$
  - Ở trường hợp này ta không thể cập nhật $low[u] = min(low[u], low[v])$ được. Vì khi ta thăm đến đỉnh $u$ mà đỉnh $v$ đã được thăm thì tức là $(u,v)$ là một cạnh nét đứt, do đó khi đi từ $u$ tới $v$ ta đã sử dụng $1$ 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 $low[]$ ) suy ra ta chỉ cập nhật $low[u]=min(low[u],num[v])$.
- **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 $u$ và các nút trong cây con $DFS$ gốc $u$ ta sẽ tiến hành cập nhật giá trị $tail[u]=$ 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 $G=(V, E)$ có $N$ $(1 \le N \le 10000)$ đỉnh và $M$ $(1 \le M \le 50000)$ 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ị $G$.

Input

Dòng đầu: chứa hai số tự nhiên $N, M$.
$M$ dòng sau mỗi dòng chứa một cặp số $(u, v)$ $(u$ khác $v$, $1 \le u \le N, 1 \le v \le N)$ mô tả một cạnh của $G$.

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 $G$.

Example

Input

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 $G$ như sau:
- Xét cây con gốc $v$ trong cây $DFS$ của $G$ có $u$ là cha trực tiếp của $v$. Gọi tập hợp các đỉnh thuộc cây con gốc $v$ là $A$, tập hợp các đỉnh không thuộc cây con gốc $v$ là $B$. Khi xoá đi cạnh $(u, v)$ thì giữa $2$ đỉnh bất kì thuộc cùng $1$ 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 $A$ với một đỉnh thuộc $B$ 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 $(u, v)$.
  - Ví dụ minh họa: Xét cạnh nét liền $(7, 9)$ với đỉnh $9$ là con trực tiếp của đỉnh $7$ trên cây $DFS$. Tập đỉnh $A$ là các đỉnh được đánh dấu màu hồng. Tập đỉnh $B$ là các đỉnh được đánh dấu màu vàng. Đỉnh $11$ thuộc tập $A$ muốn đi đến đỉnh $6$ thuộc tập $B$ bằng các cạnh nét liền thì đều phải thông qua cạnh $(7, 9)$.
- Giả sử không có cạnh nét đứt nào nối giữa $1$ đỉnh thuộc $A$ với $1$ đỉnh thuộc $B$ thì khi xoá cạnh $(u, v)$, $G$ sẽ tách ra thành $2$ vùng liên thông $A$ và $B$. Ngược lại nếu tồn tại cạnh nét đứt nối giữa $1$ đỉnh thuộc $A$ và $1$ đỉnh thuộc $B$ đồ 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 $A$ và $B$ hay không để kết luận $(u, v)$ có phải cầu không?
- Ta có từ $v$ có thể đi đến một đỉnh $p$ nào đó có $num[p]=low[v]$ bằng cách đi theo các cung của cây $DFS$ và đi qua không quá $1$ cạnh nét đứt và $p$ có thứ tự thăm sớm nhất khi $DFS$. Nếu $p$ nằm trong $B$ thì $p$ phải là tổ tiên của $v$ cũng đồng nghĩa với việc $num[p]
- Do đó nếu $low[v] \ge num[v]$ chắc chắn đỉnh $p$ thuộc cây con gốc $v$ hay $p$ thuộc tập hợp $A$ khi đó không tồn tại cạnh nét đứt nối giữa $1$ đỉnh thuộc $A$ với $1$ đỉnh thuộc $B$. Tuy nhiên, ta dễ dàng nhận thấy $low[v] \le num[v]$ vì đỉnh $v$ luôn tới được chính nó.
Kết luận: Nếu $low[v] = num[v]$ thì $(u, v)$ 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 $G$ như sau:
- Xét cây con gốc $u$ trong cây $DFS$ của $G$, nếu mọi nhánh con của $u$ đều có cung ngược lên tới tổ tiên của $u$ ($low[v] < num[u]$, với $v$ là tất cả các con trực tiếp của $u$ trên cây $DFS$) thì đỉnh $u$ không thể là đỉnh khớp. Bởi trong đồ thị ban đầu, nếu ta loại bỏ đỉnh $u$ đ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 $u$, 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 $9$ không phải là đỉnh khớp vì cả $2$ nhánh con của nó là cây con gốc $10$ và cây con gốc $13$ trong cây $DFS$ đều có cung ngược lên tới đỉnh $7$ là tổ tiên của đỉnh $9$.
- Nếu $u$ không phải là đỉnh gốc của cây $DFS$, và tồn tại ít nhất một nhánh con trong cây con gốc $u$ không có cung ngược lên một tổ tiên của $u$ ($low[v] \ge num[u]$, với $v$ là một con trực tiếp bất kì của $u$ trên cây $DFS$) thì đỉnh $u$ 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 $u$ 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 $u$. 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 $u$ thì bắt buộc phải đi qua $u$ nên việc loại bỏ đỉnh $u$ 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 $2$ là đỉnh khớp vì tồn tại $1$ nhánh con của nó là cây con gốc $4$ không có cung ngược lên tới tổ tiên của đỉnh $2$.
- Nếu $u$ là đỉnh gốc của cây $DFS$, thì $u$ là đỉnh khớp khi và chỉ khi $u$ có ít nhất $2$ nhánh con. Vì đồ thị không có cung chéo nên khi $u$ có $2$ nhánh con thì đường đi giữa hai đỉnh thuộc hai nhánh con đó bắt buộc phải đi qua $u$. Việc loại bỏ đỉnh $u$ 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 $1$ là đỉnh khớp vì đỉnh $1$ là đỉnh gốc của cây $DFS$ và có tới $3$ nhánh con.
Kết luận: Đỉnh $u$ là đỉnh khớp khi:
- Đỉnh $u$ không phải là gốc của cây $DFS$ và $low[v] \ge num[u]$ (với $v$ là một con trực tiếp bất kì của $u$ trong cây $DFS$). Hoặc
- Đỉnh $u$ là gốc của cây $DFS$ và có ít nhất $2$ con trực tiếp trong cây $DFS$.

Cài đặt

Cấu trúc dữ liệu:

Hằng số 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 8
Biến 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 9 - Thứ tự $DFS$
Biến 4 3 0 - Số lượng cạnh cầu
Mảng 4 3 1
Mảng 4 3 2 - Đánh dấu đỉnh khớp
Vector 4 3 3 - Danh sách cạnh kề của mỗi đỉnh


# include 
 
using namespace std;
const int maxN = 10010;
int n, m;
bool joint[maxN];
int timeDfs = 0, bridge = 0;
int low[maxN], num[maxN];
vector  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à $O(N + M)$.

Bài toán 2

NKPOLICE - Police

Đề 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 $N$ thành phố và $M$ đường nối $2$ chiều. Các thành phố được đánh số từ $1$ đến $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 $2$ loại truy vấn sau:

$1$. Đối với hai thành phố $A$, $B$ và một đường nối giữa hai thành phố $G1$, $G2$; hỏi tội phạm có thể di chuyển từ $A$ đến $B$ 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?
$2$. Đối với $3$ thành phố $A$, $B$, $C$; hỏi tội phạm có thể di chuyển từ $A$ đến $B$ nếu như toàn bộ thành phố $C$ 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 $2$ số nguyên $N$ và $M$ $(2 \le N \le 100000, 1 \le M \le 500000)$, số thành phố và số đường nối.
Mỗi dòng trong số $M$ dòng tiếp theo chứa $2$ số nguyên phân biệt thuộc phạm vi $[1, N]$ - 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 $Q$ $(1 \le Q \le 300000)$, số truy vấn được thử nghiệm trên hệ thống.
Mỗi dòng trong $Q$ dòng tiếp theo chứa $4$ hoặc $5$ số nguyên. Số đầu tiên cho biết loại truy vấn $1$ hoặc $2$.
- Nếu loại truy vấn là $1$, tiếp theo trên cùng dòng là $4$ số nguyên $A$, $B$, $G1$, $G2$ với ý nghĩa như đã mô tả. $A$ khác $B$; $G1$, $G2$ mô tả một con đường có sẵn.
- Nếu loại truy vấn là $2$, tiếp theo trên cùng dòng là $3$ số nguyên $A$, $B$, $C$ với ý nghĩa như đã mô tả. $A$, $B$, $C$ đô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 $Q$ 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

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ố $A$ đến thành phố $B$ thì cả $2$ thành phố $A$ và $B$ 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 $2$ thành phố $G1,$ $G2$ 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ố $A$ và $B$.
Ngược lại, nếu đường nối giữa $2$ thành phố $G1,$ $G2$ là cạnh cầu thì ta phải kiểm tra xem $2$ thành phố $A$ và $B$ có thuộc cùng một thành phần liên thông sau khi loại bỏ cạnh $(G1,G2)$ 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 $1$. Nghĩa là khi ta loại bỏ cạnh cầu $(G1,G2)$ (với $G2$ là con trực tiếp của $G1$) thì đồ thị sẽ chia ra làm $2$ 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 $G2$ của cây $DFS$.
- 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 $G2$ của cây $DFS$.
Ví dụ minh họa: Loại bỏ cạnh cầu $(1,7)$ (với đỉnh $7$ là con trực tiếp của đỉnh $1$)
Bây giờ, ta có thể xác định vị trí của $2$ đỉnh $A,$ $B$ có nằm trong cây con gốc $G2$ hay không.
- Nếu chỉ có đúng duy nhất $1$ trong $2$ đỉnh nằm trong cây con gốc $G2$ thì $2$ thành phố $A$ và $B$ không thuộc cùng một thành phần liên thông sau khi loại bỏ cạnh $(G1,G2)$.
- Ngược lại, nếu cả $2$ đỉnh cùng nằm trong cây con gốc $G2$ hoặc cả $2$ đỉnh đều không nằm trong cây con gốc $G2$ thì $2$ thành phố $A$ và $B$ đều thuộc cùng một thành phần liên thông sau khi loại bỏ cạnh $(G1,G2)$.
Nhắc lại: Nếu $num[u] \le num[v] \le tail[u]$ thì đỉnh $v$ nằm trong cây con gốc $u$ của cây $DFS$.

Truy vấn 2

Dễ thấy rằng, nếu thành phố $C$ 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ố $A$ và $B$.
Ngược lại, nếu thành phố $C$ là đỉnh khớp thì ta phải kiểm tra xem $2$ thành phố $A$ và $B$ có thuộc cùng một thành phần liên thông sau khi loại bỏ đỉnh $C$ 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 $C$ 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 $v$ là con trực tiếp của $C$ trong cây $DFS$ 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 $v$ trong cây $DFS$ nối lên tổ tiên của $C$ (đồng nghĩa với việc $low[v] \ge num[C]$). Nghĩa là khi ta loại bỏ đỉnh khớp $C$ 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à $1$ tập hợp các đỉnh thuộc cây con gốc $v$ với $v$ là con trực tiếp của $C$ trong cây $DFS$ và $low[v] \ge num[C]$.
- 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 $C$ và các đỉnh thuộc các cây con gốc $u$ với $u$ là các con trực tiếp của $C$ trong cây $DFS$ và $low[u] < num[C]$).
Ví dụ minh họa: Loại bỏ đỉnh khớp $8$. Đỉnh $11$ và $12$ là các con trực tiếp của đỉnh $8$ trong cây $DFS$. Nhưng chỉ có cây con gốc $11$ là tách riêng ra thành $1$ thành phần liên thông riêng biệt. Còn cây con gốc $12$ thì có $1$ cung ngược nối lên đỉnh $7$ (tổ tiên của đỉnh $8$) nên số lượng thành phần liên thông của cả đồ thị chỉ tăng thêm $1$.
Với mỗi đỉnh $v$ là con trực tiếp của $C$ trong cây $DFS$ và $low[v] \ge num[C]$, ta kiểm tra xem nếu chỉ có đúng duy nhất $1$ trong $2$ đỉnh nằm trong cây con gốc $v$ thì $2$ thành phố $A$ và $B$ không thuộc cùng một thành phần liên thông sau khi loại bỏ đỉnh $C$ và các cạnh liên thuộc với đỉnh $C$ đi.
Ngược lại, với $v$ là các con trực tiếp của $C$ trong cây $DFS$ và $low[v] \ge num[C]$, nếu cả $2$ đỉnh $A$ và $B$ cùng nằm trong $1$ cây con gốc $v$ hoặc cả $2$ đỉnh $A$ và $B$ đều không nằm trong bất cứ $1$ cây con gốc $v$ nào cả (đồng nghĩa với việc cả $2$ đỉnh $A,$ $B$ sẽ cùng nằm trong thành phần liên thông còn lại) thì $2$ thành phố $A$ và $B$ đều thuộc cùng một thành phần liên thông sau khi loại bỏ đỉnh $C$ và các cạnh liên thuộc với đỉnh $C$ đ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 $C$ để xác định được tổ tiên của $A$, tổ tiên của $B$. Ta có thể sử dụng $Sparse Table$ để tìm ra tổ tiên của đỉnh $A$ (hoặc $B$) là con trực tiếp của đỉnh $C$ nếu $A$ (hoặc $B$) nằm trong cây con $DFS$ gốc $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 $pa$ là tổ tiên của đỉnh $A$ và là con trực tiếp của đỉnh $C$.
Gọi đỉnh $pb$ là tổ tiên của đỉnh $B$ và là con trực tiếp của đỉnh $C$.
$A$ và $B$ thuộc cùng một thành phần liên thông sau khi loại bỏ đỉnh $C$ và các cạnh liên thuộc với đỉnh $C$ đi khi thỏa mãn một trong số các điều kiện sau:
- Nếu cả $2$ đỉnh $A$ và $B$ đều không nằm trong cây con $DFS$ gốc $C$.
- Nếu $pa = pb$ (nghĩa là cả $2$ đỉnh $A$ và $B$ đều nằm trong cây con $DFS$ gốc $pa$ ).
- Nếu $A$ không nằm trong cây con $DFS$ gốc $C$ và $B$ nằm trong cây con $DFS$ gốc $C$ sao cho $low[pb] < num[C]$ (nghĩa là có tồn tại cung ngược nối từ cây con $DFS$ gốc $pb$ lên tổ tiên của $C$ ).
- Nếu $B$ không nằm trong cây con $DFS$ gốc $C$ và $A$ nằm trong cây con $DFS$ gốc $C$ sao cho $low[pa] < num[C]$ (nghĩa là có tồn tại cung ngược nối từ cây con $DFS$ gốc $pa$ lên tổ tiên của $C$ ).
- Nếu cả $2$ đỉnh $A$ và $B$ đều nằm trong cây con $DFS$ gốc $C$ và $low[pa] < num[c]$ và $low[pb] < num[c]$ (nghĩa là cả $2$ cây con $DFS$ gốc $pa$ và cây con $DFS$ gốc $pb$ đều có cung ngược nối lên tổ tiên của $C$ )
Ngược lại, nếu không thỏa mãn tất cả các điều kiện trên thì $A$ và $B$ không thuộc cùng một thành phần liên thông sau khi loại bỏ đỉnh $C$ và các cạnh liên thuộc với đỉnh $C$ đi.
Lúc này, độ phức tạp để xử lí các truy vấn sẽ là $O(Q \cdot logN)$.

Cài đặt

Cấu trúc dữ liệu:

Hằng số 4 3 4
Biến 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 9 - Thứ tự $DFS$
Mảng 4 3 6
Mảng 4 3 7 - Lưu chiều sâu của mỗi đỉnh trong cây $DFS$
Mảng 4 3 8 - Mảng ứng dụng $Sparse Table$ với $p[i][j]$ là tổ tiên thứ $2^j$ của $i$ trong cây $DFS$
Mảng 4 3 2 - Đánh dấu đỉnh khớp
Vector 4 3 3 - Danh sách cạnh kề của mỗi đỉnh


# include 

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  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 == pre) continue;
        if (!num[v]) {
            child++;
            p[v][0] = u;
            depth[v] = depth[u] + 1;
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (u == pre) {
                if (child > 1) joint[u] = true;
            }
            else if (low[v] >= num[u]) joint[u] = true;
        }
        else low[u] = min(low[u], num[v]);
    }
    tail[u] = timeDfs;
}
/* Kiểm tra xem đỉnh u có nằm trong cây con DFS gốc root hay không? */
bool checkInSubtree(int u, int root) {
    return num[root] <= num[u] && num[u] <= tail[root];
}
/* Xử lí truy vấn 1 */
bool solve1(int a, int b, int g1, int g2) {
    /* Vì ta coi g2 là con trực tiếp của g1 nên khi g1 là con của g2, 
    ta phải đổi chỗ 2 giá trị g1 và g2 cho nhau */
    if (num[g1] > num[g2]) swap(g1, g2); 
    /* Kiểm tra nếu cạnh (g1, g2) không phải là cầu */
    if (low[g2] != num[g2]) return true;
    if (checkInSubtree(a, g2) && !checkInSubtree(b, g2)) return false;
    if (checkInSubtree(b, g2) && !checkInSubtree(a, g2)) return false;
    return true;
}
/* Xử lí truy vấn 2 */
bool solve2(int a, int b, int c) {
    if (!joint[c]) return true;
    int pa = 0, pb = 0;
    if (checkInSubtree(a, c)) pa = findParent(a, c);
    if (checkInSubtree(b, c)) pb = findParent(b, c);
    if (!pa && !pb) return true; 
    if (pa == pb) return true; 
    if (!pa && low[pb] < num[c]) return true; 
    if (!pb && low[pa] < num[c]) return true;
    if (pa && pb && low[pa] < num[c] && low[pb] < num[c]) return true;
    return false;
}
int main() {
    ios_base::sync_with_stdio(0); 
    cin.tie(0);
    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);
    }
    depth[1] = 1;
    dfs(1, 1);
    calP();
    cin >> q;
    while (q--) {
        int type, a, b, c, g1, g2;
        cin >> type;
        if (type == 1) {
            cin >> a >> b >> g1 >> g2;
            cout << (solve1(a, b, g1, g2) ? "yes\n" : "no\n");
        }
        else {
            cin >> a >> b >> c;
            cout << (solve2(a, b, c) ? "yes\n" : "no\n");
        }
    }
}

Đánh giá

Độ phức tạp của bài toán là $O(N + M + Q \cdot logN)$

Bài toán 3

KBUILD - Sửa cầu

Đề bài

Cho $N$ hòn đảo và $N - 1$ cây cầu, mỗi cây cầu nối hai hòn đảo lại với nhau. Đảm bảo rằng từ một đảo bất kì luôn có thể đến được hết mọi đảo còn lại. Pirate đưa ra một lịch trình như sau: vào mỗi ngày sẽ đi kiểm tra mọi cây cầu trên đường đi từ đảo $a$ đến đảo $b$. Hỏi sau khi Pirate thực hiện xong lịch trình đó, thì còn có bao nhiêu cây cầu chưa được kiểm tra?

Input

Dòng thứ nhất: số nguyên $N$ - số lượng hòn đảo.
$N - 1$ dòng tiếp theo: mỗi dòng chứa $2$ số nguyên $a$ và $b$ - có một cây cầu nối đảo $a$ và $b$.
Dòng thứ $N + 1$: Số nguyên $M$ - số ngày kiểm tra.
$M$ dòng tiếp theo: mỗi dòng chứa $2$ số nguyên $a$ và $b$ - ngày hôm đó, Pirate sẽ đi kiểm tra mọi cây cầu trên đường đi từ đảo $a$ đến đảo $b$.

$1 \le N, M \le 200000$

Output

Một số nguyên duy nhất thể hiện số cây cầu chưa được kiểm tra.

Input

Output

Note

Ngày thứ nhất, Pirate kiểm tra các cây cầu $(2, 3), (2, 4)$ và $(4, 6)$. Ngày thứ hai, anh kiểm tra các cây cầu $(5, 4)$ và $(4, 6)$. Cây cầu duy nhất chưa được kiểm tra là $(1, 2)$.

Phân tích

Vì đồ thị ban đầu liên thông và có $N - 1$ cạnh nên đây là đồ thị dạng cây.

Để đánh dấu các cạnh thuộc đường đi từ đỉnh $u$ đến đỉnh $v$ trên cây, thì ta có thể thêm một cạnh $(u,v)$ vào đồ thị. Khi đó, các cạnh thuộc đường đi từ $u \rightarrow v$ trên cây sẽ nằm trong $1$ chu trình. Từ đó, bài toán sẽ quy về thành bài toán đếm số lượng cạnh cầu của đồ thị.

Ví dụ minh họa: Để dánh dấu đường đi từ đỉnh $3 \rightarrow 6$ và đường đi từ đỉnh $5 \rightarrow 6$, ta thêm cạnh $(3, 6)$, $(5, 6)$ vào đồ thị. Khi đó, đồ thị có một cạnh cầu là cạnh $(1, 2)$.

Cài đặt

Cấu trúc dữ liệu:

Hằng số `

include

using namespace std; const int maxN = 10010; int n, m; bool joint[maxN]; int timeDfs = 0, bridge = 0; int low[maxN], num[maxN]; vector 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;

}

1
Biến  
  
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  
  
9 - Thứ tự $DFS$
Biến  
  
4 3  
  
0 - Số lượng cạnh cầu
Mảng  
  
4 3  
  
1
Vector  
  
4 3  
  
3 - Danh sách cạnh kề của mỗi đỉnh

include

using namespace std; const int maxN = 2e5 + 10; int n, m; int timeDfs = 0, bridge = 0; int low[maxN], num[maxN]; vector g[maxN]; 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]);
        if (low[v] == num[v]) bridge++;
    }
    else low[u] = min(low[u], num[v]);
}

} int main() {

cin >> n;
for (int i = 1; i < n; i++) {
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
}
cin >> m;
while (m--) {
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
}
dfs(1, 1);
cout << bridge;

}


### Đánh giá

Độ phức tạp của bài toán là $O(N + (N - 1 + M))$.

## Ứng dụng cây DFS trong bài toán liệt kê thành phần liên thông mạnh

## Định nghĩa

Một đồ thị có hướng là liên thông mạnh nếu như từ một đỉnh bất kì luôn tồn tại ít nhất một đường đi đến bất kì đỉnh nào khác.
Một thành phần liên thông mạnh của một đồ thị có hướng là một đồ thị con tối đại liên thông mạnh. Nếu mỗi thành phần liên thông mạnh được co lại thành một đỉnh, thì đồ thị sẽ trở thành một đồ thị có hướng không có chu trình.
Thuật toán $Kosaraju$, thuật toán $Tarjan$, và thuật toán $Gabow$ đều có thể tìm các thành phần liên thông mạnh của một đồ thị cho trước trong thời gian tuyến tính. Tuy nhiên, các thuật toán của $Tarjan$ thường được sử dụng nhiều hơn do chúng chỉ cần thực hiện tìm kiếm theo chiều sâu một lần trong khi thuật toán của $Kosaraju$ cần hai lần.

![](http://https://i0.wp.com/vnoi.info/wiki/uploads/Depth-First-Search-Tree_img14.png)

## Một số định lý quan trọng

Định lý 1: Nếu $a$, $b$ là hai đỉnh thuộc thành phần liên thông mạnh $C$ thì với mọi đường đi từ $a$ tới $b$ cũng như từ $b$ tới $a$. Tất cả đỉnh trung gian trên đường đi đó đều phải thuộc $C$. Chứng minh: Nếu $a$ và $b$ là hai đỉnh thuộc $C$ thì tức là có một đường đi từ $a$ đến $b$ và một đường khác đi từ $b$ về $a$. Suy ra với một đỉnh $v$ nằm trên đường đi từ $a$ tới $b$ thì $a$ tới được $v$, $v$ tới được $b$, mà $b$ có đường tới $a$ nên $v$ cũng tới được $a$. Vậy $v$ nằm trong thành phần liên thông mạnh chứa $a$ tức là $v$ thuộc $C$. Tương tự với một đỉnh nằm trên đường đi từ $b$ tới $a$.
Định lý 2: Với một thành phần liên thông mạnh $C$ bất kỳ, tồn tại một đỉnh $r$ thuộc $C$ sao cho mọi đỉnh của $C$ đều thuộc cây con gốc $r$ trong cây $DFS$. Chứng minh: Trước hết, nhắc lại một thành phần liên thông mạnh là một đồ thị con liên thông mạnh của đồ thị ban đầu thoả mãn tính chất tối đại tức là việc thêm vào thành phần đó một tập hợp đỉnh khác sẽ làm mắt đi tính liên thông mạnh.  
Trong số các đỉnh của $C$, chọn $r$ là đỉnh được thăm đầu tiên theo thuật toán tìm kiếm theo chiều sâu. Ta sẽ chứng minh $C$ nằm trong nhánh $DFS$ gốc $r$. Thật vậy, với một đỉnh $v$ bất kỳ của $C$, do $C$ liên thông mạnh nên phải tồn tại một đường đi từ $r$ tới $v$: $(r = x\_0, x\_1,…, x\_k = v)$  
Từ định lý $1$, tất cả các đỉnh $x\_1, x\_2,…, x\_k$ đều thuộc $C$ nên chúng sẽ phải thăm sau đỉnh $r$. Khi thủ tục $DFS(r)$ được gọi thì tất cả các đỉnh $x\_1, x\_2,…, x\_k$ đều chưa thăm; vì thủ tục $DFS(r)$ sẽ liệt kê tất cả những đỉnh chưa thăm đến được từ $r$ bằng cách xây dựng nhánh gốc $r$ của cây $DFS$, nên các đỉnh $x\_1, x\_2,…, x\_k = v$ sẽ thuộc nhánh gốc $r$ của cây $DFS$. Bởi chọn $v$ là đỉnh bất kỳ trong $C$ nên ta có điều phải chứng minh.  
Đỉnh $r$ trong chứng minh định lý - đỉnh thăm trước tất cả các đỉnh khác trong $C$ - gọi là chốt của thành phần $C$. Mỗi thành phần liên thông mạnh có duy nhất một chốt. Xét về vị trí trong cây tìm kiếm $DFS$, chốt của một thành phân liên thông là đỉnh nằm cao nhất so với các đỉnh khác thuộc thành phần đó, hay nói cách khác: là tiền bối của tất cả các đỉnh thuộc thành phần đó.
Định lý 3: Luôn tìm được đỉnh chốt $a$ thỏa mãn: Quá trình tìm kiếm theo chiều sâu bắt đầu từ $a$ không thăm được bất kỳ một chốt nào khác. (Tức là nhánh $DFS$ gốc $a$ không chứa một chốt nào ngoài $a$) chẳng hạn ta chọn $a$ là chốt được thăm sau cùng trong một dây chuyền đệ quy hoặc chọn $a$ là chốt thăm sau tất cả các chốt khác. Với chốt $a$ như vậy thì các đỉnh thuộc nhánh $DFS$ gốc $a$ chính là thành phần liên thông mạnh chứa $a$. Chứng minh: Với mọi đỉnh $v$ nằm trong nhánh $DFS$ gốc $a$, xét $b$ là chốt của thành phần liên thông mạnh chứa $v$. Ta sẽ chứng minh $a = b$. Thật vậy, theo định lý $2$, $v$ phải nằm trong nhánh $DFS$ gốc $b$. Vậy $v$ nằm trong cả nhánh $DFS$ gốc $a$ và nhánh $DFS$ gốc $b$. Giả sử phản chứng rằng $a$ khác $b$ thì sẽ có hai trường hợp xảy ra:  
Trường hợp 1: Nhánh $DFS$ gốc $a$ chứa nhánh $DFS$ gốc $b$, có nghĩa là thủ tục $DFS(b)$ sẽ do thủ tục $DFS(a)$ gọi tới, điều này mâu thuẫn với giả thiết rằng $a$ là chốt mà quá trình tìm kiếm theo chiều sâu bắt đầu từ $a$ không thăm một chốt nào khác.  
Trường hợp 2: Nhánh $DFS$ gốc $a$ nằm trong nhánh $DFS$ gốc $b$, có nghĩa là $a$ nằm trên một đường đi từ $b$ tới $v$. Do $b$ và $v$ thuộc cùng một thành phần liên thông mạnh nên theo định lý $1$, $a$ cũng phải thuộc thành phần liên thông mạnh đó. Vậy thì thành phần liên thông mạnh này có hai chốt $a$ và $b$. Điều này vô lý.  
Theo định lý $2$, ta đã có thành phân liên thông mạnh chứa $a$ nằm trong nhánh $DFS$ gốc $a$, theo chứng minh trên ta lại có: Mọi đỉnh trong nhánh $DFS$ gốc $a$ nằm trong thành phân liên thông mạnh chứa $a$. Kết hợp lại được: Nhánh $DFS$ gốc $a$ chính là thành phần liên thông mạnh chứa $a$.

## Bài toán 4

TJALG - Tìm TPLT mạnh

### Đề bài

Cho đồ thị $G(V, E)$ có hướng $N$ $(1 \\le N \\le 10^4)$ đỉnh, $M$ $(1 \\le M \\le 10^5)$ cung. Hãy đếm số thành phần liên thông mạnh của $G$.

Input

Dòng đầu tiên là $N, M$.
$M$ dòng tiếp theo mô tả một cung của $G$.

Output

Gồm một dòng duy nhất là số TPLT mạnh.

Examples

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


0

Output

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


1

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


2

Output

1


### Thuật toán Tarjan

![](http://https://i0.wp.com/vnoi.info/wiki/uploads/Depth-First-Search-Tree_img15.png)

Thuật toán Tarjan được xây dựng dựa trên các dữ kiện sau:

Tìm kiếm $DFS$ tạo ra cây/ rừng $DFS$
Các thành phần liên thông mạnh tạo thành các cây con của cây $DFS$.
Nếu ta có thể tìm được đỉnh gốc của các cây con như vậy, ta có thể in/ lưu trữ tất cả các nút trong cây con đó (bao gồm cả đỉnh gốc) và đó sẽ là một thành phần liên thông mạnh $(Strongly$ $Connected$ $Components$ - $SCC).$
Không có cung ngược từ $SCC$ này sang $SCC$ khác (Có thể có các cung chéo, nhưng các cung chéo sẽ không được sử dụng trong khi xử lý đồ thị).

#### Mô tả thuật toán

![](http://https://i0.wp.com/vnoi.info/wiki/uploads/Depth-First-Search-Tree_gif2.gif)

#### Ý tưởng

Nhận xét: Xét cây con gốc $u$ trong cây $DFS$. Gọi tập hợp các đỉnh thuộc cây con gốc $u$ là $A$, tập hợp các đỉnh không thuộc cây con gốc $u$ là $B$. Nếu tồn tại $1$ đỉnh $x$ thuộc $A$ tới được $1$ đỉnh $y$ thuộc $B$ thì $y$ phải có thứ tự thăm sớm hơn $u$. Vì nếu $y$ được thăm sau $u$ ta có thể duyệt từ $u$ qua $x$ tới $y$ khi đó $y$ sẽ trở thành con của $u$.
Đầu tiên ta thực hiện $DFS$ kết hợp tính mảng $low\[\], num\[\]$ như đã trình bày ở trên. Song song với việc này, khi duyệt tới đỉnh $u$ ta sẽ thực hiện đẩy $u$ vào $stack$.
Khi đã duyệt xong đỉnh $u$ (sau khi duyệt hết toàn bộ các đỉnh nằm trong cây con $DFS$ gốc $u$), nếu $num\[u\] = low\[u\]$ thì đây chính là đỉnh có thứ tự thăm sớm nhất của một thành phần liên thông mạnh.
Khi đó ta sẽ loại bỏ tất cả các đỉnh trong thành phần liên thông mạnh này ra khỏi đồ thị và các đỉnh này là các đỉnh đang nằm trên $u$ trong $stack$ hiện tại vì các đỉnh này chính là các đỉnh nằm trên cây con gốc $u$ trong cây $DFS$ do các nút được đẩy vào $stack$ theo thứ tự thăm.
Mặt khác, giả sử ta có đỉnh $x$ thuộc cây con gốc $u$ và $x$ thuộc một thành phần liên thông mạnh không chứa $u$ có đỉnh có thứ tự thăm sớm nhất là $y$, dễ thấy $y$ phải là con của $u$ nên thời điểm duyệt xong của $y$ sớm hơn $u$ chứng tỏ $y$ và thành phần liên thông mạnh chứa nó sẽ bị loại bỏ trước đó không còn trong $stack$ nữa (nếu $y$ không phải con $u$ thì vô lí vì ta đang xét mọi đỉnh trong cây con gốc $u$ chưa được xác định nằm trong thành phần liên thông mạnh nào hiện tại không tới được các đỉnh không nằm trong cây con gốc $u$).
Ta sẽ đánh dấu tất cả các đỉnh thuộc thành phần liên thông mạnh này bằng $1$ mảng để sau này không xét lại đỉnh đấy nữa. Đồng thời, ta loại bỏ cách đỉnh này ra khỏi $stack$ để không làm ảnh hưởng tới các đỉnh khác vẫn còn nằm trong đồ thị.

### Cài đặt

Cấu trúc dữ liệu:

Hằng số  
  
4 3  
  
4
Biến  
  
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  
  
9 - Thứ tự $DFS$
Biến  
`  

# include   
   
using namespace std;  
const int maxN = 10010;  
int n, m;  
bool joint[maxN];  
int timeDfs = 0, bridge = 0;  
int low[maxN], num[maxN];  
vector  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;  
}

8 - Số lượng thành phần liên thông mạnh

Mảng 4 3 1
Mảng 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 0 - Đánh dấu các đỉnh đã bị xóa
Vector 4 3 3 - Danh sách cạnh kề của mỗi đỉnh
Ngăn xếp 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 2 - Lưu lại các đỉnh trong thành phần liên thông mạnh

4

Đánh giá

Độ phức tạp của thuật toán $Tarjan$ là $O(N + M)$

Bài toán 5

KCOLLECT - Thu hoạch

Đề bài

Khu vườn của Pirate có hình chữ nhật, và được chia thành $M \cdot N$ ô vuông bằng nhau. Trong mỗi ô vuông có một cây thuộc một loại quả khác nhau, đánh số từ $0$ đến $9$. Những con số này thể hiện giá trị kinh tế của các loại cây. Tuy nhiên, nhìn mặt con Robot trái cây này có vẻ ngu ngu nên trong lần đầu tiên thử việc, Pirate muốn test AI của nó. Cụ thể là Robot phải tuân theo các quy định sau:

Tại mỗi ô, Robot chỉ có thể đi sang hướng đông hoặc hướng nam sang ô kề cạnh.
Có một số ô đặc biệt mà tại đó Robot có thể đi được thêm hướng tây hoặc hướng bắc sang ô kề cạnh (chỉ một trong hai).
Robot không được đi vào những ô có cây dừa.
Robot được đi qua một ô nhiều lần. Khi đi qua một ô, Robot phải hái hết quả ở cây trong ô đó. Lợi nhuận thu được sẽ bằng chỉ số của loại cây vừa được thu hái. Và sau này, không thể đạt thêm lợi nhuận gì từ ô đó nữa.

Xuất phát từ ô ở góc tây bắc của khu vườn, hãy giúp Robot trái cây xác định hành trình để đạt được lợi nhuận tối đa.

mẹo hay Thuật toán DFS Depth First Search DFS Vietnam Dfs là gì DFS geeksforgeeks Thuật toán Dijkstra

Bài toán duyệt đồ thị theo chiều sâu

Ứng dụng cây DFS trong bài toán tìm khớp, cầu

Định nghĩa

Bài toán 1

Đề bài

Phân tích

Tìm cạnh cầu

Tìm đỉnh khớp

Cài đặt

Đánh giá

Bài toán 2

Đề bài

Phân tích

Truy vấn 1

Truy vấn 2

Cài đặt

Đánh giá

Bài toán 3

Đề bài

Phân tích

Cài đặt

include

include

Đánh giá

Bài toán 5

Đề bài

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội