DFS Tree

Cầu và low

Chạy DFS, gán $tin_u$ khi vào $u$. Định nghĩa $low_u$ là $tin$ nhỏ nhất chạm tới được từ cây con của $u$ bằng cách đi xuống theo cạnh cây rồi dùng tối đa một cạnh ngược. Tính khi DFS lùi về: $low_u = \min(tin_u,\ tin_w \text{ với mọi cạnh ngược } u \text{-} w,\ low_v \text{ với mọi con } v)$.

Cạnh cây $(u, v)$ (với $v$ là con) là cầu khi và chỉ khi $low_v > tin_u$: cây con của $v$ không có cạnh ngược nào lên tới $u$ hay cao hơn, nên bỏ cạnh $(u, v)$ thì cây con đó tách ra. Cạnh ngược không bao giờ là cầu vì nó nằm trên một chu trình. Khi đi xuống, bỏ qua đúng cạnh vừa đi tới (theo chỉ số cạnh, không theo đỉnh cha), để cạnh song song tới cha vẫn được tính là cạnh ngược.

void dfs(ll u, ll pe) {
    tin[u] = low[u] = ++timer;
    for (pair<ll, ll> e : g[u]) {
        ll v = e.first, id = e.second;
        if (id == pe) continue;
        if (tin[v]) low[u] = min(low[u], tin[v]);
        else {
            dfs(v, id);
            low[u] = min(low[u], low[v]);
            if (low[v] > tin[u]) isb[id] = 1;
        }
    }
}

Ví dụNhững Tuyến Đường Không Thể Thiếu

Đề. Đồ thị vô hướng đơn liên thông $n \le 10^5$ đỉnh, $m \le 2 \cdot 10^5$ cạnh. In mọi cầu, đầu nhỏ trước, sắp theo thứ tự từ điển.

Lời giải. DFS tính tin và low như trên. Cạnh cây $(u, v)$ là cầu khi low[v] > tin[u]: không cạnh ngược nào từ cây con của $v$ chạm tới $u$ hay cao hơn, nên bỏ cạnh đó thì cây con tách ra.

Bước 1: DFS theo chỉ số cạnh. pe là chỉ số cạnh vừa đi xuống $u$; bỏ qua đúng cạnh đó, mọi cạnh tới đỉnh đã thăm khác là cạnh ngược và cập nhật low[u] bằng tin[v]. Sau khi gọi xong con $v$, low[u] nhận low[v]: cạnh ngược từ cây con của $v$ cũng là đường vòng của $u$.

void dfs(ll u, ll pe) {
    tin[u] = low[u] = ++timer;
    for (pair<ll, ll> e : g[u]) {
        ll v = e.first, id = e.second;
        if (id == pe) continue;
        if (tin[v]) low[u] = min(low[u], tin[v]);
        else {
            dfs(v, id);
            low[u] = min(low[u], low[v]);
            if (low[v] > tin[u]) isb[id] = 1;
        }
    }
}

Bước 2: gom và sắp. Đưa đầu nhỏ lên trước rồi sắp theo cặp để in đúng thứ tự đề đòi.

for (ll i = 1; i <= m; i++)
    if (isb[i]) res.push_back({min(eu[i], ev[i]), max(eu[i], ev[i])});
sort(res.begin(), res.end());

Đệ quy sâu tới $10^5$ tầng; thường vẫn chạy được với ngăn xếp mặc định của trình chấm, nhưng đồ thị lớn hơn thì nên viết bằng ngăn xếp tường minh như bài 76.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 1e5 + 5, M = 2e5 + 5;
ll n, m, timer, tin[N], low[N], eu[M], ev[M], isb[M];
vector<pair<ll, ll>> g[N];

void dfs(ll u, ll pe) {
    tin[u] = low[u] = ++timer;
    for (pair<ll, ll> e : g[u]) {
        ll v = e.first, id = e.second;
        if (id == pe) continue;
        if (tin[v]) low[u] = min(low[u], tin[v]);
        else {
            dfs(v, id);
            low[u] = min(low[u], low[v]);
            if (low[v] > tin[u]) isb[id] = 1;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        cin >> eu[i] >> ev[i];
        g[eu[i]].push_back({ev[i], i});
        g[ev[i]].push_back({eu[i], i});
    }
    dfs(1, 0);
    vector<pair<ll, ll>> res;
    for (ll i = 1; i <= m; i++)
        if (isb[i]) res.push_back({min(eu[i], ev[i]), max(eu[i], ev[i])});
    sort(res.begin(), res.end());
    cout << res.size() << '\n';
    for (pair<ll, ll> p : res) cout << p.first << ' ' << p.second << '\n';
}

ChạyInput6 7
1 2
2 3
3 1
3 4
4 5
5 6
6 4

Output1
3 4

Độ phức tạp: $O(n + m)$ cộng phần sắp kết quả.

Cách ngây thơ là bỏ từng cạnh rồi kiểm liên thông bằng một lượt DFS:

DFS với $low$ nhanh hơn cỡ hàng nghìn lần, và khoảng cách còn tăng theo cỡ đồ thị vì một bên $O(n + m)$, bên kia $O(m(n + m))$.

Khớp

Đỉnh $u$ không phải gốc là khớp khi và chỉ khi nó có một con $v$ với $low_v \ge tin_u$: cây con của $v$ không có cạnh ngược nào vượt lên trên $u$, nên bỏ $u$ thì cây con đó tách khỏi phần phía trên. Lần này dấu bằng được phép, vì cạnh ngược về chính $u$ cũng mất khi bỏ $u$.

Gốc không có phía trên, nên cần quy tắc riêng: gốc là khớp khi và chỉ khi nó có ít nhất hai con trong cây DFS. Các cây con của gốc không nối với nhau bằng cạnh ngang (DFS không có cạnh ngang), nên bỏ gốc thì chúng tách rời.

Với đồ thị nhiều thành phần, gọi DFS từ mọi đỉnh chưa thăm, mỗi lần là một gốc mới. Hai điều kiện cầu và khớp có thể tính trong cùng một vòng, và chỉ khác nhau ở dấu: > cho cầu, >= cho khớp.

Ví dụNhững Thành Phố Trọng Yếu

Đề. Đồ thị vô hướng đơn liên thông $n \le 10^5$ đỉnh, $m \le 2 \cdot 10^5$ cạnh. In số khớp và các khớp tăng dần.

Lời giải. Hai quy tắc khớp như trên. Đỉnh không phải gốc là khớp khi có con $v$ với low[v] >= tin[u]: dấu bằng được phép vì cạnh ngược chạm đúng $u$ cũng mất khi bỏ $u$. Gốc là khớp khi có từ hai con trở lên trong cây DFS. Đồ thị đơn nên bỏ qua đỉnh cha là đủ; có cạnh song song thì phải bỏ theo chỉ số cạnh như ví dụ trước.

Bước 1: DFS có đếm con. child đếm số con trong cây DFS, chỉ dùng cho gốc; kiểm quy tắc gốc sau khi duyệt hết hàng xóm.

void dfs(ll u, ll p) {
    tin[u] = low[u] = ++timer;
    ll child = 0;
    for (ll v : g[u]) {
        if (v == p) continue;
        if (tin[v]) low[u] = min(low[u], tin[v]);
        else {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            child++;
            if (p && low[v] >= tin[u]) cut[u] = 1;
        }
    }
    if (!p && child >= 2) cut[u] = 1;
}

Bước 2: in các khớp tăng dần. Duyệt $u = 1..n$ thì tự tăng dần.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 1e5 + 5;
ll n, m, timer, tin[N], low[N], cut[N];
vector<ll> g[N];

void dfs(ll u, ll p) {
    tin[u] = low[u] = ++timer;
    ll child = 0;
    for (ll v : g[u]) {
        if (v == p) continue;
        if (tin[v]) low[u] = min(low[u], tin[v]);
        else {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            child++;
            if (p && low[v] >= tin[u]) cut[u] = 1;
        }
    }
    if (!p && child >= 2) cut[u] = 1;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    vector<ll> res;
    for (ll u = 1; u <= n; u++)
        if (cut[u]) res.push_back(u);
    cout << res.size() << '\n';
    for (ll u : res) cout << u << ' ';
    cout << '\n';
}

ChạyInput6 7
1 2
2 3
3 1
3 4
4 5
5 6
6 4

Output2
3 4

Độ phức tạp: $O(n + m)$.

Liên thông mạnh

Trên đồ thị có hướng, hai đỉnh liên thông mạnh khi mỗi đỉnh đi tới được đỉnh kia. Quan hệ này chia đỉnh thành các thành phần liên thông mạnh (strongly connected component, SCC). Thuật toán Kosaraju dùng hai lần DFS:

1. DFS trên đồ thị gốc, ghi các đỉnh theo thứ tự xong (đã duyệt hết các đỉnh đi ra).
2. DFS trên đồ thị ngược, lấy đỉnh theo thứ tự xong giảm dần; mỗi lần gọi từ ngoài thu được đúng một SCC.

Đỉnh xong muộn nhất thuộc một SCC “nguồn” của đồ thị nén. Trên đồ thị ngược, từ nó chỉ tới được các đỉnh trong chính SCC đó, vì các cung vào SCC nguồn trong đồ thị gốc không tồn tại. Lấy SCC đó ra rồi lặp lại với phần còn lại. Tổng $O(n + m)$. Thuật toán Tarjan làm trong một lần DFS bằng ngăn xếp và $low$, cho các SCC theo thứ tự tô pô ngược; Kosaraju cho chúng theo thứ tự tô pô xuôi.

Ví dụPhân Vùng Tương Hỗ

Đề. Đồ thị có hướng $n \le 10^5$ đỉnh, $m \le 2 \cdot 10^5$ cung. In số SCC và nhãn SCC của từng đỉnh.

Lời giải. Kosaraju, hai lần DFS. Lần một trên đồ thị gốc ghi thứ tự xong. Lần hai duyệt theo thứ tự xong giảm dần trên đồ thị ngược: mỗi đỉnh chưa có nhãn mở một SCC mới, và DFS trên đồ thị ngược từ nó chỉ lan được trong đúng SCC đó, vì các SCC tới được từ nó trên đồ thị ngược đều đã có nhãn từ trước.

Bước 1: đồ thị gốc và đồ thị ngược. Dựng cùng lúc khi đọc cung.

g[u].push_back(v);
rg[v].push_back(u);

Bước 2: thứ tự xong. dfs1 đẩy $u$ vào ord khi đã duyệt xong mọi đỉnh đi ra từ nó; gọi từ mọi đỉnh chưa thăm.

void dfs1(ll u) {
    vis[u] = 1;
    for (ll v : g[u])
        if (!vis[v]) dfs1(v);
    ord.push_back(u);
}

Bước 3: gán nhãn trên đồ thị ngược. comp dùng 0 làm “chưa có nhãn”, nên nhãn bắt đầu từ 1.

void dfs2(ll u) {
    comp[u] = k;
    for (ll v : rg[u])
        if (!comp[v]) dfs2(v);
}

for (ll i = n - 1; i >= 0; i--)
    if (!comp[ord[i]]) {
        k++;
        dfs2(ord[i]);
    }

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 1e5 + 5;
ll n, m, k, vis[N], comp[N];
vector<ll> g[N], rg[N], ord;

void dfs1(ll u) {
    vis[u] = 1;
    for (ll v : g[u])
        if (!vis[v]) dfs1(v);
    ord.push_back(u);
}

void dfs2(ll u) {
    comp[u] = k;
    for (ll v : rg[u])
        if (!comp[v]) dfs2(v);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        rg[v].push_back(u);
    }
    for (ll u = 1; u <= n; u++)
        if (!vis[u]) dfs1(u);
    for (ll i = n - 1; i >= 0; i--)
        if (!comp[ord[i]]) {
            k++;
            dfs2(ord[i]);
        }
    cout << k << '\n';
    for (ll u = 1; u <= n; u++) cout << comp[u] << ' ';
    cout << '\n';
}

ChạyInput6 7
1 2
2 3
3 1
3 4
4 5
5 4
5 6

Output3
1 1 1 2 2 3

Độ phức tạp: $O(n + m)$.

Nén đồ thị

Nén mỗi SCC thành một đỉnh và giữ các cung nối hai SCC khác nhau: được một DAG, vì một chu trình giữa các SCC sẽ gộp chúng thành một. Nhiều bài trên đồ thị có hướng tổng quát trở thành bài trên DAG: số đỉnh nguồn cần chọn để tới được mọi nơi là số SCC có bậc vào 0; đường thu nhiều giá trị nhất là đường dài nhất trên DAG với trọng số SCC bằng tổng các đỉnh trong đó. Nhãn của Kosaraju đã theo thứ tự tô pô, nên quy hoạch động chỉ cần duyệt nhãn theo thứ tự ngược.

Ví dụHành Trình Thu Thập

Đề. Đồ thị có hướng $n \le 10^5$ đỉnh có giá trị dương, $m \le 2 \cdot 10^5$ cung. Đi từ đỉnh tùy ý theo các cung, mỗi đỉnh thu giá trị một lần. Tìm tổng lớn nhất.

Lời giải. Trong một SCC đi được hết mọi đỉnh rồi rời đi, nên mỗi SCC có giá trị bằng tổng các đỉnh của nó, và bài thành tìm đường có tổng lớn nhất trên đồ thị nén (không chu trình). Kosaraju gán nhãn theo thứ tự tô pô xuôi: mọi cung nén đi từ nhãn nhỏ sang nhãn lớn, nên quy hoạch động duyệt nhãn từ lớn về nhỏ.

Bước 1: Kosaraju như các ví dụ trước.

Bước 2: dựng đồ thị nén. val[c] là tổng giá trị các đỉnh của SCC $c$; dg[c] là các SCC kề sau $c$. Có thể có cung lặp, không sao vì chỉ lấy max.

for (ll u = 1; u <= n; u++) {
    val[comp[u]] += w[u];
    for (ll v : g[u])
        if (comp[u] != comp[v]) dg[comp[u]].push_back(comp[v]);
}

Bước 3: đường tổng lớn nhất. dp[c] là tổng lớn nhất của một đường bắt đầu ở SCC $c$; duyệt $c$ từ $k$ về 1 thì dp của các SCC kề sau đã xong. Đáp án là max mọi dp[c], vì được xuất phát ở đỉnh tùy ý.

for (ll c = k; c >= 1; c--) {
    dp[c] = 0;
    for (ll d : dg[c]) dp[c] = max(dp[c], dp[d]);
    dp[c] += val[c];
    ans = max(ans, dp[c]);
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 1e5 + 5;
ll n, m, k, w[N], vis[N], comp[N], val[N], dp[N];
vector<ll> g[N], rg[N], dg[N], ord;

void dfs1(ll u) {
    vis[u] = 1;
    for (ll v : g[u])
        if (!vis[v]) dfs1(v);
    ord.push_back(u);
}

void dfs2(ll u) {
    comp[u] = k;
    for (ll v : rg[u])
        if (!comp[v]) dfs2(v);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= n; i++) cin >> w[i];
    for (ll i = 1; i <= m; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        rg[v].push_back(u);
    }
    for (ll u = 1; u <= n; u++)
        if (!vis[u]) dfs1(u);
    for (ll i = n - 1; i >= 0; i--)
        if (!comp[ord[i]]) {
            k++;
            dfs2(ord[i]);
        }
    for (ll u = 1; u <= n; u++) {
        val[comp[u]] += w[u];
        for (ll v : g[u])
            if (comp[u] != comp[v]) dg[comp[u]].push_back(comp[v]);
    }
    ll ans = 0;
    for (ll c = k; c >= 1; c--) {
        dp[c] = 0;
        for (ll d : dg[c]) dp[c] = max(dp[c], dp[d]);
        dp[c] += val[c];
        ans = max(ans, dp[c]);
    }
    cout << ans << '\n';
}

ChạyInput6 7
4 2 7 3 5 1
1 2
2 3
3 1
3 4
4 5
5 4
5 6

Output22

Độ phức tạp: $O(n + m)$.

Định hướng cạnh

Đồ thị vô hướng liên thông định hướng được thành đồ thị liên thông mạnh khi và chỉ khi nó không có cầu (định lý Robbins). Một cầu, theo hướng nào, cũng chỉ cho đi một chiều giữa hai phía. Ngược lại, khi không có cầu, định hướng theo DFS: cạnh cây từ cha xuống con, cạnh ngược từ con cháu lên tổ tiên. Từ gốc đi xuống được mọi đỉnh; từ mỗi đỉnh, cây con của nó luôn có một cạnh ngược vượt lên trên ($low_v < tin_v$ vì không có cầu), nên từng bước leo được về gốc.

Ví dụĐịnh Hướng Bền Vững

Đề. Đồ thị vô hướng đơn liên thông $n \le 10^5$ đỉnh, $m \le 3 \cdot 10^5$ cạnh. Định hướng mọi cạnh để được đồ thị liên thông mạnh, in hướng theo thứ tự cạnh; không được thì in 0.

Lời giải. Định lý Robbins: đồ thị vô hướng liên thông định hướng được thành liên thông mạnh khi và chỉ khi nó không có cầu. Cách định hướng lấy thẳng từ cây DFS: cạnh cây hướng từ cha xuống con, cạnh ngược hướng từ đỉnh dưới lên tổ tiên. Không có cầu thì từ gốc đi xuống được mọi đỉnh theo cạnh cây, và từ mỗi đỉnh leo về được gốc bằng các cạnh ngược, nên đồ thị liên thông mạnh.

Bước 1: định hướng lúc xét cạnh lần đầu. Mỗi cạnh xuất hiện ở hai danh sách kề; used[id] cho biết đã định hướng chưa, lần đầu xét thì ghi u → v với $u$ là đỉnh đang đứng. Lần đầu xét cạnh tới $v$ chưa thăm là cạnh cây, đúng hướng cha xuống con. Lần đầu xét cạnh tới $v$ đã thăm thì $v$ là tổ tiên còn trên ngăn xếp (nếu $v$ là con cháu đã xong thì cạnh đã được xét từ phía $v$), nên hướng đi lên tổ tiên.

if (!used[id]) {
    used[id] = 1;
    da[id] = u;
    db[id] = v;
}

Bước 2: tìm cầu trong cùng lượt DFS. Có cầu thì không định hướng được, in 0.

if (tin[v]) low[u] = min(low[u], tin[v]);
else {
    dfs(v, id);
    low[u] = min(low[u], low[v]);
    if (low[v] > tin[u]) bad = 1;
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 1e5 + 5, M = 3e5 + 5;
ll n, m, timer, tin[N], low[N], da[M], db[M], used[M];
bool bad;
vector<pair<ll, ll>> g[N];

void dfs(ll u, ll pe) {
    tin[u] = low[u] = ++timer;
    for (pair<ll, ll> e : g[u]) {
        ll v = e.first, id = e.second;
        if (id == pe) continue;
        if (!used[id]) {
            used[id] = 1;
            da[id] = u;
            db[id] = v;
        }
        if (tin[v]) low[u] = min(low[u], tin[v]);
        else {
            dfs(v, id);
            low[u] = min(low[u], low[v]);
            if (low[v] > tin[u]) bad = 1;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }
    dfs(1, 0);
    if (bad) {
        cout << 0 << '\n';
        return 0;
    }
    for (ll i = 1; i <= m; i++) cout << da[i] << ' ' << db[i] << '\n';
}

ChạyInput5 6
1 2
2 3
3 1
3 4
4 5
5 3

Output1 2
2 3
3 1
3 4
4 5
5 3

Độ phức tạp: $O(n + m)$.