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

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

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

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 $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]= num[u]] joint[u] = true; } else low[u] = min[low[u], num[v]]; } } int main[] { cin >> n >> m; for [int i = 1; i > u >> v; g[u].push_back[v]; g[v].push_back[u]; } for [int i = 1; i m; for [int i = 1; i > 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 > a >> b >> c; cout 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 > u >> v;  
        g[u].push_back[v];  
        g[v].push_back[u];  
    }  
    for [int i = 1; i > 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  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 > u >> v;  
            g[u].push_back[v];  
            g[v].push_back[u];  
        }  
        for [int i = 1; i