DFS and BFS

IDanh sách kề và DFS

Một con đường đi được cả hai chiều là cạnh vô hướng; đường một chiều là cạnh có hướng. Đi từ đỉnh này sang đỉnh kia qua các cạnh là một đường đi; đường đi quay về chỗ cũ là một chu trình. Hai đỉnh liên thông khi có đường đi giữa chúng.

Để lưu đồ thị, mỗi đỉnh giữ danh sách các hàng xóm của nó: g[u] là các đỉnh nối với $u$. Cạnh vô hướng thì thêm vào danh sách của cả hai đầu. Cách lưu này gọi là danh sách kề; nó tốn bộ nhớ đúng bằng số đỉnh cộng số cạnh, và muốn xét hàng xóm của $u$ thì chỉ việc đi qua g[u].

DFS đi như người thám hiểm mê cung mang theo cuộn chỉ: tới một đỉnh thì đánh dấu đã đến, gặp ngả nào chưa đi thì rẽ vào và đi tới cùng. Hết đường thì lần theo cuộn chỉ quay về ngả rẽ gần nhất, thử ngả khác. Mỗi đỉnh được ghé một lần, mỗi cạnh được xét hai lần (một lần từ mỗi đầu), nên cả lượt là $O(n + m)$ với $n$ đỉnh và $m$ cạnh.

void dfs(ll u) {
    vis[u] = 1;
    for (ll v : g[u])
        if (!vis[v]) dfs(v);
}

Một lượt DFS từ $u$ đánh dấu đúng những đỉnh tới được từ $u$: cả thành phần liên thông chứa $u$. Muốn đếm có bao nhiêu thành phần, cứ đi lần lượt các đỉnh; gặp đỉnh nào chưa đánh dấu thì đó là một thành phần mới, đếm nó rồi DFS từ đó.

DFS đệ quy sâu tới $n$ tầng. Với đồ thị cỡ $10^6$ đỉnh, nhất là lưới, nên đổi sang BFS hoặc tự giữ ngăn xếp để khỏi tràn bộ nhớ ngăn xếp. Đề có nhiều test thì chỉ xóa g[u] và vis[u] của những đỉnh đã dùng, đừng xóa cả mảng lớn mỗi test.

Ví dụSố Cụm Trong Mạng

Đề. Đồ thị vô hướng $n \le 100$ đỉnh, đếm số thành phần liên thông.

Lời giải. Duyệt $u = 1..n$, gặp đỉnh chưa thăm thì tăng đếm và DFS từ đó. DFS đánh dấu đúng thành phần chứa $u$, nên đỉnh chưa thăm tiếp theo chắc chắn thuộc một thành phần mới: nếu nó thuộc thành phần đã gặp thì DFS trước đó đã đánh dấu nó rồi. Mỗi thành phần được đếm đúng một lần.

Bước 1: danh sách kề. Cạnh vô hướng thêm vào cả hai đầu.

for (ll i = 1; i <= m; i++) {
    ll u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
}

Bước 2: DFS. Đánh dấu $u$ rồi gọi tiếp mọi hàng xóm chưa thăm. Khi hàm trả về, mọi đỉnh tới được từ $u$ đã được đánh dấu.

void dfs(ll u) {
    vis[u] = 1;
    for (ll v : g[u])
        if (!vis[v]) dfs(v);
}

Bước 3: đếm số lần phải bắt đầu.

for (ll u = 1; u <= n; u++)
    if (!vis[u]) {
        ans++;
        dfs(u);
    }

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

const ll N = 105;
ll n, m, vis[N];
vector<ll> g[N];

void dfs(ll u) {
    vis[u] = 1;
    for (ll v : g[u])
        if (!vis[v]) dfs(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);
        g[v].push_back(u);
    }
    ll ans = 0;
    for (ll u = 1; u <= n; u++)
        if (!vis[u]) {
            ans++;
            dfs(u);
        }
    cout << ans << '\n';
}

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

Output3

IIBFS

BFS loang ra như vết mực thấm trên giấy. Đỉnh xuất phát cách chính nó 0 bước. Mọi hàng xóm của nó cách 1 bước. Hàng xóm của những đỉnh ấy mà chưa gặp thì cách 2 bước, và cứ thế. Lớp gần luôn được xử lý xong trước lớp xa, nên lần đầu tiên chạm tới một đỉnh cũng là lúc đi tới nó bằng ít cạnh nhất.

Để giữ đúng thứ tự gần trước xa sau, BFS dùng một hàng đợi: lấy đỉnh $u$ ở đầu hàng, mỗi hàng xóm $v$ chưa gặp nhận d[v] = d[u] + 1 rồi xếp vào cuối hàng.

Đánh dấu một đỉnh ngay lúc xếp nó vào hàng, không phải lúc lấy ra, để mỗi đỉnh vào hàng đúng một lần. Muốn in đường đi, lưu par[v] = u khi $v$ được gặp từ $u$. Từ đích lần theo par về nguồn, rồi đảo ngược là được đường đi. BFS chỉ cho đường ngắn nhất khi mọi cạnh dài như nhau; cạnh có độ dài khác nhau cần Dijkstra (bài 3.5).

Ví dụTuyến Truyền Tin Ngắn Nhất

Đề. $n \le 10^5$ máy, $m \le 2 \cdot 10^5$ kết nối hai chiều. In một tuyến từ máy 1 tới máy $n$ qua ít máy nhất, hoặc IMPOSSIBLE.

Lời giải. BFS từ máy 1 cho khoảng cách ngắn nhất (theo số cạnh) tới mọi máy. Để in được tuyến, ghi lại par[v]: đỉnh đã đưa $v$ vào hàng đợi. Mỗi đỉnh chỉ có một par, và đi theo par từ $n$ lùi về 1 là một đường ngắn nhất, vì mỗi bước lùi giảm khoảng cách đúng 1.

Bước 1: BFS có ghi cha. d[v] = -1 là chưa thăm. Đánh dấu ngay lúc đẩy vào hàng đợi, nên mỗi đỉnh vào hàng một lần.

for (ll i = 1; i <= n; i++) d[i] = -1;
queue<ll> q;
q.push(1);
d[1] = 0;
while (!q.empty()) {
    ll u = q.front();
    q.pop();
    for (ll v : g[u])
        if (d[v] == -1) {
            d[v] = d[u] + 1;
            par[v] = u;
            q.push(v);
        }
}

Bước 2: truy vết. Máy $n$ không được thăm thì in IMPOSSIBLE. Ngược lại lần par từ $n$ về 1; đường lần ngược đi từ $n$ về 1 nên reverse trước khi in. Số máy trên đường là d[n] + 1, chính là path.size().

vector<ll> path;
for (ll v = n; v != 1; v = par[v]) path.push_back(v);
path.push_back(1);
reverse(path.begin(), path.end());

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

const ll N = 1e5 + 5;
ll n, m, d[N], par[N];
vector<ll> g[N];

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);
    }
    for (ll i = 1; i <= n; i++) d[i] = -1;
    queue<ll> q;
    q.push(1);
    d[1] = 0;
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        for (ll v : g[u])
            if (d[v] == -1) {
                d[v] = d[u] + 1;
                par[v] = u;
                q.push(v);
            }
    }
    if (d[n] == -1) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    vector<ll> path;
    for (ll v = n; v != 1; v = par[v]) path.push_back(v);
    path.push_back(1);
    reverse(path.begin(), path.end());
    cout << path.size() << '\n';
    for (ll v : path) cout << v << ' ';
    cout << '\n';
}

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

Output4
1 2 3 7

Khi đồ thị cỡ triệu đỉnh, cách lưu cũng đáng chú ý. vector cho mỗi đỉnh là nhiều khối nhớ nhỏ rải rác. Nếu đếm bậc trước rồi xếp mọi cạnh vào một mảng liên tiếp, BFS đọc bộ nhớ gọn hơn:

Mảng liên tiếp nhanh hơn khoảng 2,6 lần. Với đồ thị cỡ $2 \cdot 10^5$ thì vector vẫn thừa nhanh; chỉ nghĩ tới cách này khi đồ thị cỡ triệu cạnh và hết thời gian.

IIILưới

Lưới $n \times m$ cũng là một đồ thị: mỗi ô là một đỉnh, nối với các ô chung cạnh không phải tường. Không cần dựng danh sách kề. Hai mảng dx, dy liệt kê bốn hướng lên, xuống, trái, phải; từ ô $(x, y)$, đi theo hướng $k$ tới ô $(x + dx_k, y + dy_k)$, miễn ô đó còn trong lưới và không phải tường.

Bấm vào ô để dựng hay phá tường, và xem BFS loang ra:

Lưới $1000 \times 1000$ đã có $10^6$ đỉnh, nên DFS đệ quy rất dễ tràn ngăn xếp. Dùng BFS với hàng đợi các cặp tọa độ:

ll dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
queue<pair<ll, ll>> q;
q.push({sx, sy});
d[sx][sy] = 0;
while (!q.empty()) {
    ll x = q.front().first, y = q.front().second;
    q.pop();
    for (ll k = 0; k < 4; k++) {
        ll nx = x + dx[k], ny = y + dy[k];
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
        if (s[nx][ny] == '#' || d[nx][ny] != -1) continue;
        d[nx][ny] = d[x][y] + 1;
        q.push({nx, ny});
    }
}

Muốn in đường đi trên lưới thì không cần lưu cả ô cha: chỉ cần nhớ hướng $k$ đã đi để vào mỗi ô. Từ đích, lùi ngược theo hướng đã ghi là về được xuất phát, và các hướng gom được (đảo lại) chính là chuỗi bước đi.

IVHai màu và chu trình

Đồ thị hai phía. Có chia được các đỉnh thành hai nhóm, sao cho mọi cạnh đều nối hai nhóm khác nhau không? Cứ thử tô: đỉnh đầu tô màu 1, mọi hàng xóm của nó buộc phải màu 2, hàng xóm của chúng buộc phải màu 1, và cứ thế lan ra bằng BFS. Không có lựa chọn nào cả, nên nếu gặp một cạnh hai đầu cùng màu thì chắc chắn không chia được. Điều đó xảy ra đúng khi đồ thị có một chu trình độ dài lẻ: đi vòng quanh nó, màu đổi ở mỗi cạnh, số lần đổi lẻ nên về tới chỗ cũ thì màu đã ngược.

Tìm chu trình trong đồ thị vô hướng. Các cạnh mà DFS đi xuống tạo thành một cây, gọi là cây DFS. Trong lúc DFS, nếu từ đỉnh đang đứng thấy một hàng xóm đã thăm mà không phải đỉnh vừa đi tới mình, thì hàng xóm đó là một tổ tiên trên đường đang đi. Cạnh ấy gọi là cạnh ngược; nó cùng đoạn đường trên cây DFS khép thành một chu trình. Lần par từ đỉnh hiện tại về tổ tiên đó là in được chu trình. Đồ thị có hướng cần thêm một trạng thái “đang trên đường đi”, sẽ gặp ở bài 3.3.

Ví dụChia Hai Nhóm Tương Khắc

Đề. $n \le 10^5$ người, $m \le 2 \cdot 10^5$ cặp không được cùng nhóm. In nhóm (1 hoặc 2) của từng người, hoặc IMPOSSIBLE.

Lời giải. Bài hỏi đồ thị có hai phía không. Tô hai màu bằng BFS: mỗi thành phần bắt đầu ở một đỉnh chưa tô với màu 1, hàng xóm nhận màu ngược lại. Thành phần khác nhau không ràng buộc nhau. Gặp một cạnh hai đầu cùng màu nghĩa là có chu trình lẻ, không chia được.

Bước 1: tô một thành phần. col[v] = 0 là chưa tô; màu là 1 hoặc 2, nên 3 - c đổi màu. Mọi cạnh được kiểm khi lấy đầu mút ra khỏi hàng đợi.

queue<ll> q;
q.push(s);
col[s] = 1;
while (!q.empty()) {
    ll u = q.front();
    q.pop();
    for (ll v : g[u]) {
        if (!col[v]) {
            col[v] = 3 - col[u];
            q.push(v);
        } else if (col[v] == col[u]) {
            cout << "IMPOSSIBLE\n";
            return 0;
        }
    }
}

Bước 2: mọi thành phần. Vòng ngoài chạy $s = 1..n$, bỏ qua đỉnh đã tô.

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

const ll N = 1e5 + 5;
ll n, m, col[N];
vector<ll> g[N];

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);
    }
    for (ll s = 1; s <= n; s++) {
        if (col[s]) continue;
        queue<ll> q;
        q.push(s);
        col[s] = 1;
        while (!q.empty()) {
            ll u = q.front();
            q.pop();
            for (ll v : g[u]) {
                if (!col[v]) {
                    col[v] = 3 - col[u];
                    q.push(v);
                } else if (col[v] == col[u]) {
                    cout << "IMPOSSIBLE\n";
                    return 0;
                }
            }
        }
    }
    for (ll i = 1; i <= n; i++) cout << col[i] << ' ';
    cout << '\n';
}

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

Output1 2 1 1 2 1

VNhiều nguồn và đỉnh phụ

Hai mẹo nhỏ biến nhiều bài trông khác hẳn thành đúng một lần BFS.

Nhiều nguồn. Đề hỏi, với mọi đỉnh, khoảng cách tới đỉnh gần nhất thuộc một tập $S$. Đừng BFS từ từng đỉnh. Hãy xếp cả tập $S$ vào hàng đợi ngay từ đầu, khoảng cách 0, rồi BFS một lần. Như thể có một đỉnh nguồn ảo nối tới mọi đỉnh của $S$: lớp 0 là cả tập $S$, lớp 1 là mọi đỉnh kề với $S$, và cứ thế.

Nếu cạnh có hướng mà câu hỏi lại là “từ $u$ đi tới tập $S$ mất bao lâu”, thì BFS trên đồ thị ngược (đảo chiều mọi cạnh), xuất phát từ $S$. Đường từ $u$ tới $S$ trong đồ thị gốc chính là đường từ $S$ tới $u$ trong đồ thị ngược.

Ví dụBước Nhảy Đổi Tính Chẵn Lẻ

Đề. Mảng $n \le 2 \cdot 10^5$ số, từ $i$ nhảy được tới $i - a_i$ hoặc $i + a_i$ nếu còn trong mảng. Với mỗi $i$, in số bước ít nhất để tới một vị trí có $a_j$ khác tính chẵn lẻ với $a_i$, hoặc $-1$.

Lời giải. Bước nhảy là cạnh có hướng $i \to i \pm a_i$. Với vị trí $a_i$ lẻ, đáp án là khoảng cách từ $i$ tới tập các vị trí chẵn. BFS từ từng $i$ thì quá chậm; đảo chiều mọi cạnh, khoảng cách từ $i$ tới tập nguồn trên đồ thị gốc bằng khoảng cách từ tập nguồn tới $i$ trên đồ thị ngược, và BFS nhiều nguồn tính được nó cho mọi $i$ một lần. Làm hai lần: nguồn là các vị trí chẵn, rồi nguồn là các vị trí lẻ.

Bước 1: đồ thị ngược. rg[t] chứa mọi $i$ nhảy được tới $t$.

for (ll i = 1; i <= n; i++) {
    if (i - a[i] >= 1) rg[i - a[i]].push_back(i);
    if (i + a[i] <= n) rg[i + a[i]].push_back(i);
}

Bước 2: BFS nhiều nguồn. Nguồn là mọi vị trí có $a_i$ chia 2 dư $p$, khoảng cách 0, cùng vào hàng đợi trước khi BFS. Chỉ ghi ans[i] cho các vị trí có tính chẵn lẻ khác $p$, đúng những vị trí cần tới tập nguồn này.

void bfs(ll p) {
    queue<ll> q;
    for (ll i = 1; i <= n; i++) {
        d[i] = -1;
        if (a[i] % 2 == p) {
            d[i] = 0;
            q.push(i);
        }
    }
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        for (ll v : rg[u])
            if (d[v] == -1) {
                d[v] = d[u] + 1;
                q.push(v);
            }
    }
    for (ll i = 1; i <= n; i++)
        if (a[i] % 2 != p) ans[i] = d[i];
}

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

const ll N = 2e5 + 5;
ll n, a[N], d[N], ans[N];
vector<ll> rg[N];

void bfs(ll p) {
    queue<ll> q;
    for (ll i = 1; i <= n; i++) {
        d[i] = -1;
        if (a[i] % 2 == p) {
            d[i] = 0;
            q.push(i);
        }
    }
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        for (ll v : rg[u])
            if (d[v] == -1) {
                d[v] = d[u] + 1;
                q.push(v);
            }
    }
    for (ll i = 1; i <= n; i++)
        if (a[i] % 2 != p) ans[i] = d[i];
}

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

    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    for (ll i = 1; i <= n; i++) {
        if (i - a[i] >= 1) rg[i - a[i]].push_back(i);
        if (i + a[i] <= n) rg[i + a[i]].push_back(i);
    }
    bfs(0);
    bfs(1);
    for (ll i = 1; i <= n; i++) cout << ans[i] << ' ';
    cout << '\n';
}

ChạyInput5
1 2 1 2 1

Output1 -1 1 -1 1

Đỉnh phụ. Có khi cái tốn chi phí không phải là đi qua một cạnh, mà là đổi một thứ gì đó: đổi tuyến xe, đổi màu, đổi phương tiện. Khi đó thêm một đỉnh mới cho chính thứ được đổi. Ví dụ mỗi tuyến xe buýt thành một đỉnh, nối với mọi ga mà tuyến đi qua. Lên một tuyến rồi xuống ở ga khác là hai cạnh, nên số tuyến phải đi bằng nửa khoảng cách BFS. Số cạnh mới chỉ bằng số cặp (ga, tuyến); nếu nối thẳng mọi cặp ga cùng tuyến thì có thể tới cỡ $n^2$ cạnh.

VIQuy hoạch động trên cây

Cây là đồ thị liên thông không có chu trình: $n$ đỉnh, đúng $n - 1$ cạnh, và giữa hai đỉnh bất kỳ có đúng một đường đi. Chọn một đỉnh làm gốc, chẳng hạn đỉnh 1, rồi treo cây xuống. Lúc này mỗi đỉnh khác gốc có đúng một cha là đỉnh ngay phía trên, các đỉnh ngay phía dưới là con, và cả phần treo dưới một đỉnh là cây con của nó.

Rất nhiều câu hỏi trên cây có cùng một dáng: đáp án ở một đỉnh tính được từ đáp án ở các con của nó. Ví dụ đơn giản nhất là kích thước cây con, tức số đỉnh trong cây con của $u$: bằng 1 (chính $u$) cộng kích thước cây con của từng con. Cái khó duy nhất là thứ tự: phải tính con xong trước cha.

DFS đệ quy làm được điều này một cách tự nhiên, nhưng cây có thể là một đường dài $2 \cdot 10^5$ đỉnh, đệ quy sâu chừng ấy tầng dễ tràn ngăn xếp. Cách an toàn là BFS từ gốc rồi lấy thứ tự gặp đỉnh ord. Trong thứ tự này cha luôn đứng trước con, nên đi ngược ord thì con luôn xong trước cha:

for (ll i = 1; i <= n; i++) sz[i] = 1;
for (ll i = n - 1; i >= 1; i--) sz[par[ord[i]]] += sz[ord[i]];

Khi mỗi đỉnh có hai lựa chọn, ta giữ hai con số. Bài kinh điển: chọn nhiều đỉnh nhất sao cho không có hai đỉnh được chọn nào nối với nhau bằng một cạnh. Gọi f1[u] là số đỉnh chọn được nhiều nhất trong cây con của $u$ khi chọn $u$, f0[u] là con số đó khi không chọn $u$.

• Chọn $u$ thì không con nào được chọn: f1[u] bằng 1 cộng tổng f0 của các con.
• Không chọn $u$ thì mỗi con tự do chọn hay không, lấy cách tốt hơn: f0[u] bằng tổng, qua các con, của số lớn hơn giữa f0 và f1.

Bấm chạy để xem các con số đi từ lá lên gốc; cuối cùng các đỉnh được chọn hiện màu cam:

Viết thành code, mỗi đỉnh xong thì đẩy phần của nó lên cha:

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

const ll N = 2e5 + 5;
ll n, par[N], vis[N], f0[N], f1[N];
vector<ll> g[N];

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

    cin >> n;
    for (ll i = 1; i < n; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<ll> ord;
    queue<ll> q;
    q.push(1);
    vis[1] = 1;
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        ord.push_back(u);
        for (ll v : g[u])
            if (!vis[v]) {
                vis[v] = 1;
                par[v] = u;
                q.push(v);
            }
    }
    for (ll i = n - 1; i >= 0; i--) {
        ll u = ord[i];
        f1[u] += 1;
        if (i == 0) continue;
        f0[par[u]] += max(f0[u], f1[u]);
        f1[par[u]] += f0[u];
    }
    cout << max(f0[1], f1[1]) << '\n';
}

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

Output4

Bài ghép cặp nhiều cạnh nhất trên cây đi theo đúng khuôn này, chỉ đổi ý nghĩa hai con số. Khi trạng thái còn kèm một con số đếm, kiểu “chọn đúng $k$ đỉnh trong cây con”, ta gộp bảng của từng con vào bảng của cha như bài ba lô. Gộp sao cho mỗi bảng chỉ dài bằng kích thước cây con thì tổng cả cây chỉ $O(n^2)$, vì mỗi cặp đỉnh chỉ “gặp nhau” một lần ở chỗ hai nhánh của chúng hợp lại.

Ví dụChọn Đại Diện Sửa Đường

Đề. Cây $n \le 10^5$ khu vực, trụ sở ở khu vực 1. Mỗi đường là loại 1 (bình thường) hoặc loại 2 (cần sửa). Chọn một khu vực nghĩa là cử người ở đó đi theo đường duy nhất về khu vực 1 và sửa mọi đường loại 2 trên đường đi. Chọn ít khu vực nhất để mọi đường loại 2 đều được sửa; in số lượng và danh sách.

Lời giải. Treo cây từ khu vực 1. Xét một đường loại 2 nối $v$ với cha của nó. Người đi qua đường này phải xuất phát từ đâu đó trong cây con của $v$. Vậy có hai trường hợp:

• Cây con của $v$ đã có người được chọn: người đó đi về gốc chắc chắn đi qua đường này, không cần làm gì thêm.
• Chưa có ai: bắt buộc chọn thêm một người trong cây con của $v$. Chọn ngay $v$ là tốt nhất, vì người ở $v$ sửa được đúng đường này, và mọi đường phía trên mà người ở sâu hơn sửa được thì người ở $v$ cũng sửa được.

Ghi has[v] = 1 khi cây con của $v$ đã có người được chọn. Đi ngược thứ tự BFS để con xong trước cha; mỗi đỉnh xong thì báo lên cha nếu cây con mình đã có người. Mỗi lần chọn đều bắt buộc, nên số người là ít nhất. Đề cho in danh sách theo thứ tự bất kỳ; ta sắp lại cho gọn.

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

const ll N = 1e5 + 5;
ll n, par[N], typ[N], vis[N], has[N];
vector<pair<ll, ll>> g[N];

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

    cin >> n;
    for (ll i = 1; i < n; i++) {
        ll u, v, t;
        cin >> u >> v >> t;
        g[u].push_back({v, t});
        g[v].push_back({u, t});
    }
    vector<ll> ord;
    queue<ll> q;
    q.push(1);
    vis[1] = 1;
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        ord.push_back(u);
        for (pair<ll, ll> e : g[u])
            if (!vis[e.first]) {
                vis[e.first] = 1;
                par[e.first] = u;
                typ[e.first] = e.second;
                q.push(e.first);
            }
    }
    vector<ll> ans;
    for (ll i = n - 1; i >= 1; i--) {
        ll v = ord[i];
        if (typ[v] == 2 && !has[v]) {
            has[v] = 1;
            ans.push_back(v);
        }
        if (has[v]) has[par[v]] = 1;
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for (ll v : ans) cout << v << ' ';
    cout << '\n';
}

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

Output2
4 6

VIIĐường kính và tâm

Đường kính của cây là đường đi dài nhất giữa hai đỉnh. Tìm nó chỉ cần hai lần BFS:

1. BFS từ một đỉnh bất kỳ, lấy đỉnh xa nhất, gọi là $a$.
2. BFS từ $a$, lấy đỉnh xa nhất, gọi là $b$. Đường từ $a$ tới $b$ là một đường kính.

Vì sao đỉnh xa nhất ở lượt 1 lại là một đầu đường kính? Ý chính của chứng minh: giả sử không phải. Lấy một đường kính thật, nối đoạn đường đi tới $a$ với nửa dài hơn của đường kính ấy, ta luôn được một đường còn dài hơn đường kính, vô lý. Lý luận này cần mọi cạnh có độ dài không âm.

Một cách khác là quy hoạch động: ở mỗi đỉnh $u$, giữ độ sâu lớn nhất của hai nhánh đi xuống dài nhất từ hai con khác nhau. Đường dài nhất có điểm cao nhất là $u$ bằng tổng hai nhánh đó; đường kính là giá trị lớn nhất qua mọi $u$. Cách này dùng được cả khi cạnh có trọng số âm.

Tâm của cây là đỉnh nằm giữa đường kính: một đỉnh nếu đường kính có số cạnh chẵn, hai đỉnh kề nhau nếu lẻ. Đứng ở tâm thì khoảng cách tới đỉnh xa nhất là nhỏ nhất. Một hệ quả hay dùng: với mọi đỉnh $u$, đỉnh xa $u$ nhất luôn là $a$ hoặc $b$, nên chỉ cần thêm một lần BFS từ $b$ là có khoảng cách tới đỉnh xa nhất của mọi đỉnh.

Ví dụBa Đỉnh Phủ Nhiều Cạnh

Đề. Cây $n \le 2 \cdot 10^5$ đỉnh. Chọn ba đỉnh khác nhau $a, b, c$ sao cho hợp ba đường đi giữa từng cặp chứa nhiều cạnh nhất. In số cạnh đó và một bộ ba.

Lời giải. Hợp ba đường giữa ba đỉnh là phần cây nhỏ nhất nối cả ba. Lấy hai đầu của một đường kính làm $a$ và $b$ là tốt nhất: chúng đã phủ được đường dài nhất có thể. Khi đó thêm $c$ chỉ góp phần đường từ $c$ tới chỗ gần nhất trên đường kính. Vậy cần đỉnh xa đường kính nhất, và đó đúng là BFS nhiều nguồn: xếp mọi đỉnh trên đường kính vào hàng đợi với khoảng cách 0. Đáp án là độ dài đường kính cộng khoảng cách của $c$.

Cả bài là ba lần BFS. Hàm bfs nhận một danh sách nguồn, nên dùng chung được cho cả hai lượt tìm đường kính lẫn lượt nhiều nguồn. Có một chỗ dễ sót: khi mọi đỉnh đều nằm trên đường kính, $c$ vẫn phải khác $a$ và $b$, nên ta chọn $c$ trong các đỉnh khác hai đầu.

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

const ll N = 2e5 + 5;
ll n, d[N], par[N];
vector<ll> g[N];

void bfs(vector<ll> src) {
    for (ll i = 1; i <= n; i++) d[i] = -1;
    queue<ll> q;
    for (ll s : src) {
        d[s] = 0;
        par[s] = s;
        q.push(s);
    }
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        for (ll v : g[u])
            if (d[v] == -1) {
                d[v] = d[u] + 1;
                par[v] = u;
                q.push(v);
            }
    }
}

ll far() {
    ll best = 1;
    for (ll i = 2; i <= n; i++)
        if (d[i] > d[best]) best = i;
    return best;
}

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

    cin >> n;
    for (ll i = 1; i < n; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    bfs({1});
    ll a = far();
    bfs({a});
    ll b = far(), len = d[b];
    vector<ll> path;
    for (ll v = b; v != a; v = par[v]) path.push_back(v);
    path.push_back(a);
    bfs(path);
    ll c = 0;
    for (ll v = 1; v <= n; v++)
        if (v != a && v != b && (c == 0 || d[v] > d[c])) c = v;
    cout << len + d[c] << '\n' << a << ' ' << b << ' ' << c << '\n';
}

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

Output5
6 1 4