DFS and BFS

Danh sách kề và DFS

Vài chữ dùng suốt chương. Cạnh vô hướng đi được cả hai chiều, cạnh có hướng chỉ đi theo chiều mũi tên. Bậc của một đỉnh là số cạnh nối với nó. Đường đi là dãy đỉnh mà hai đỉnh liền nhau có cạnh nối; chu trình là đường đi quay về đỉnh đầu. Hai đỉnh liên thông khi có đường đi giữa chúng.

Đồ thị $n$ đỉnh, $m$ cạnh lưu bằng danh sách kề: g[u] là các đỉnh nối với $u$, mỗi cạnh vô hướng thêm vào cả hai đầu. Bộ nhớ $O(n + m)$, duyệt hàng xóm của $u$ tốn đúng bậc của $u$. Ma trận kề $n \times n$ chỉ hợp khi $n$ cỡ vài nghìn.

DFS từ $u$: đánh dấu $u$ đã thăm, rồi gọi DFS cho từng hàng xóm chưa thăm. Mỗi đỉnh được gọi một lần, mỗi cạnh được xét hai lần, nên tổng $O(n + m)$. Gọi DFS từ mọi đỉnh chưa thăm, mỗi lần gọi từ ngoài là một thành phần liên thông mới. Đệ quy sâu tới $n$ tầng; với $n$ cỡ $10^6$ trên lưới, nên đổi sang BFS hoặc tự giữ ngăn xếp.

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

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ó. 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;
using 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';
}

Input7 4
1 2
2 3
4 5
6 7

Output3

Mỗi đỉnh và mỗi cạnh được xét một lần: $O(n + m)$.

BFS theo lớp khoảng cách

BFS dùng một hàng đợi. Đỉnh xuất phát có khoảng cách 0; lấy đỉnh $u$ ở đầu hàng, mỗi hàng xóm $v$ chưa thăm nhận d[v] = d[u] + 1 và vào cuối hàng. Hàng đợi luôn chứa các đỉnh khoảng cách $k$ rồi tới $k + 1$, không bao giờ lẫn lớp xa hơn, nên mọi đỉnh lớp $k$ được lấy ra trước mọi đỉnh lớp $k + 1$ và d[v] là số cạnh ít nhất từ nguồn tới $v$. Đánh dấu thăm lúc đẩy vào hàng, không phải lúc lấy ra, để mỗi đỉnh vào hàng một lần.

Muốn in đường đi, lưu par[v] = u khi $v$ được thăm từ $u$; từ đích lần par về nguồn rồi đảo ngược. BFS chỉ đúng khi mọi cạnh cùng độ dài; cạnh có trọng số cần Dijkstra (bài 34).

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;
using 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';
}

Input7 7
1 2
2 3
3 7
1 4
4 5
5 6
6 7

Output4
1 2 3 7

$O(n + m)$.

Lưới là đồ thị

Lưới $n \times m$ là đồ thị mà mỗi ô là một đỉnh, nối với các ô chung cạnh không bị chặn. Không cần dựng danh sách kề: giữ hai mảng dx, dy cho bốn hướng (hoặc tám hướng), và một hàm kiểm ô nằm trong lưới. Lưới $1000 \times 1000$ có $10^6$ đỉnh, nên DFS đệ quy dễ tràn ngăn xếp; dùng BFS với hàng đợi các cặp tọa độ. Truy vết trên lưới chỉ cần nhớ hướng đã đi vào mỗi ô.

Ví dụNhững Vùng Trống

Đề. Lưới $n, m \le 1000$ gồm . và #. Đếm số vùng . liên thông bốn hướng.

Lời giải. Như đếm thành phần liên thông, chỉ đổi đồ thị thành lưới: mỗi ô . là một đỉnh, nối với các ô . chung cạnh. Gặp ô . chưa thăm thì tăng đếm và loang hết vùng của nó. Dùng BFS thay cho DFS đệ quy vì một vùng có thể có $10^6$ ô, quá sâu cho ngăn xếp.

Bước 1: loang một vùng. dx, dy là bốn hướng lên, xuống, trái, phải. Hai dòng continue loại ô ra ngoài lưới, ô tường và ô đã thăm. Hàng đợi chứa thẳng cặp tọa độ, không cần đánh số ô.

void bfs(ll sx, ll sy) {
    queue<pair<ll, ll>> q;
    q.push({sx, sy});
    vis[sx][sy] = 1;
    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] == '#' || vis[nx][ny]) continue;
            vis[nx][ny] = 1;
            q.push({nx, ny});
        }
    }
}

Bước 2: đếm vùng. Vòng ngoài đếm số lần phải bắt đầu một vùng mới.

for (ll i = 0; i < n; i++)
    for (ll j = 0; j < m; j++)
        if (s[i][j] == '.' && !vis[i][j]) {
            ans++;
            bfs(i, j);
        }

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

const ll N = 1005;
ll n, m, vis[N][N];
ll dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
string s[N];

void bfs(ll sx, ll sy) {
    queue<pair<ll, ll>> q;
    q.push({sx, sy});
    vis[sx][sy] = 1;
    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] == '#' || vis[nx][ny]) continue;
            vis[nx][ny] = 1;
            q.push({nx, ny});
        }
    }
}

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

    cin >> n >> m;
    for (ll i = 0; i < n; i++) cin >> s[i];
    ll ans = 0;
    for (ll i = 0; i < n; i++)
        for (ll j = 0; j < m; j++)
            if (s[i][j] == '.' && !vis[i][j]) {
                ans++;
                bfs(i, j);
            }
    cout << ans << '\n';
}

Input5 7
##..###
#...#.#
###.#.#
#..##..
#..##..

Output3

Mỗi ô vào hàng đợi một lần: $O(nm)$.

Ví dụLối Ra Ngắn Nhất

Đề. Lưới $n, m \le 1000$ có tường, một ô A và một ô B. In YES, độ dài và chuỗi bước LRUD của một đường ngắn nhất từ A tới B, hoặc NO.

Lời giải. BFS trên lưới từ A. Thay vì lưu ô cha, lưu hướng đã đi để vào mỗi ô: from[x][y] = k. Từ B lùi ngược theo hướng đã ghi là về được A, và các hướng gom được chính là chuỗi bước, theo thứ tự ngược.

Bước 1: tìm A, B và khởi tạo. from[x][y] = -1 là chưa thăm; ô xuất phát đặt 4 để khác $-1$ mà không trùng hướng nào. Hướng $k$ ứng với chữ "UDLR"[k], khớp với dx, dy.

for (ll i = 0; i < n; i++) {
    cin >> s[i];
    for (ll j = 0; j < m; j++) {
        from[i][j] = -1;
        if (s[i][j] == 'A') ax = i, ay = j;
        if (s[i][j] == 'B') bx = i, by = j;
    }
}

Bước 2: BFS ghi hướng. Như loang vùng, chỉ thêm from[nx][ny] = k lúc thăm ô mới.

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] == '#' || from[nx][ny] != -1) continue;
    from[nx][ny] = k;
    q.push({nx, ny});
}

Bước 3: truy vết. Đứng ở B, lấy hướng k đã vào ô này, ghi chữ dir[k], rồi lùi một bước ngược hướng đó. Chữ cái gom được theo thứ tự từ B về A, nên đảo lại trước khi in.

string path;
for (ll x = bx, y = by; x != ax || y != ay;) {
    ll k = from[x][y];
    path += dir[k];
    x -= dx[k];
    y -= dy[k];
}
reverse(path.begin(), path.end());

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

const ll N = 1005;
ll n, m, from[N][N];
ll dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
string s[N], dir = "UDLR";

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

    cin >> n >> m;
    ll ax = 0, ay = 0, bx = 0, by = 0;
    for (ll i = 0; i < n; i++) {
        cin >> s[i];
        for (ll j = 0; j < m; j++) {
            from[i][j] = -1;
            if (s[i][j] == 'A') ax = i, ay = j;
            if (s[i][j] == 'B') bx = i, by = j;
        }
    }
    queue<pair<ll, ll>> q;
    q.push({ax, ay});
    from[ax][ay] = 4;
    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] == '#' || from[nx][ny] != -1) continue;
            from[nx][ny] = k;
            q.push({nx, ny});
        }
    }
    if (from[bx][by] == -1) {
        cout << "NO\n";
        return 0;
    }
    string path;
    for (ll x = bx, y = by; x != ax || y != ay;) {
        ll k = from[x][y];
        path += dir[k];
        x -= dx[k];
        y -= dy[k];
    }
    reverse(path.begin(), path.end());
    cout << "YES\n" << path.size() << '\n' << path << '\n';
}

Input5 6
######
#A...#
###.##
#...B#
######

OutputYES
5
RRDDR

$O(nm)$.

Tô hai màu và tìm chu trình

Đồ thị hai phía. Một đồ thị chia được đỉnh thành hai phía, mọi cạnh nối hai phía khác nhau, khi và chỉ khi nó không có chu trình độ dài lẻ. Kiểm bằng cách duyệt từng thành phần và tô màu: đỉnh đầu màu 1, hàng xóm của đỉnh màu $c$ nhận màu $3 - c$. Gặp một cạnh hai đầu cùng màu là vô nghiệm; không gặp thì cách tô đó là một cách chia.

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: đỉnh gọi DFS cho $v$ là cha của $v$, các đỉnh trên đường từ đỉnh xuất phát xuống $u$ là tổ tiên của $u$. Trong DFS, cạnh tới một đỉnh đã thăm mà không phải cha là một cạnh ngược: nó nối đỉnh hiện tại với một tổ tiên, và cùng đường đi trên cây DFS tạo thành 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 ba trạng thái (chưa thăm, đang trên ngăn xếp, đã xong), sẽ gặp ở bài 32.

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;
using 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';
}

Input6 4
1 2
2 3
4 5
5 6

Output1 2 1 1 2 1

$O(n + m)$.

Ví dụMột Chuyến Đi Khép Kín

Đề. Đồ thị vô hướng đơn $n \le 10^5$ đỉnh, $m \le 2 \cdot 10^5$ cạnh. In một chu trình đơn (đỉnh đầu lặp lại ở cuối), hoặc IMPOSSIBLE.

Lời giải. DFS từ mọi đỉnh chưa thăm. Ở đỉnh $u$, gặp hàng xóm $v$ đã thăm và khác par[u] thì $v$ là tổ tiên của $u$: đồ thị vô hướng không có cạnh ngang trong DFS. Khi đó chu trình là $v, u, \mathrm{par}[u], \dots, v$. Đồ thị đơn nên không có hai cạnh giữa cùng một cặp đỉnh, cạnh tới cha chính là cạnh vừa đi xuống, và chu trình tìm được có ít nhất ba đỉnh.

Bước 1: DFS dừng sớm. dfs trả về bool để dừng mọi lời gọi ngay khi đã tìm được chu trình. Bỏ qua đúng đỉnh cha; gặp đỉnh đã thăm khác cha thì lần par từ $u$ lên tới $v$ để ghi chu trình, đặt $v$ ở cả đầu và cuối như đề yêu cầu.

bool dfs(ll u) {
    vis[u] = 1;
    for (ll v : g[u]) {
        if (v == par[u]) continue;
        if (vis[v]) {
            cyc.push_back(v);
            for (ll x = u; x != v; x = par[x]) cyc.push_back(x);
            cyc.push_back(v);
            return 1;
        }
        par[v] = u;
        if (dfs(v)) return 1;
    }
    return 0;
}

Bước 2: thử từ mọi đỉnh. Đồ thị có thể không liên thông; thành phần nào có chu trình thì in ngay và kết thúc.

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

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

bool dfs(ll u) {
    vis[u] = 1;
    for (ll v : g[u]) {
        if (v == par[u]) continue;
        if (vis[v]) {
            cyc.push_back(v);
            for (ll x = u; x != v; x = par[x]) cyc.push_back(x);
            cyc.push_back(v);
            return 1;
        }
        par[v] = u;
        if (dfs(v)) return 1;
    }
    return 0;
}

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 u = 1; u <= n; u++)
        if (!vis[u] && dfs(u)) {
            cout << cyc.size() << '\n';
            for (ll x : cyc) cout << x << ' ';
            cout << '\n';
            return 0;
        }
    cout << "IMPOSSIBLE\n";
}

Input6 5
1 2
2 3
3 4
4 1
5 6

Output5
1 4 3 2 1

$O(n + m)$.

BFS từ nhiều nguồn và đồ thị ngược

Muốn biết 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, mà đẩy cả tập $S$ vào hàng đợi với 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$. Khi cạnh có hướng mà câu hỏi lại là “từ $u$ tới gần nhất tập $S$”, BFS trên đồ thị ngược (đảo chiều mọi cạnh) từ $S$: đường từ $u$ tới $S$ trong đồ thị gốc 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;
using 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';
}

Input5
1 2 1 2 1

Output1 -1 1 -1 1

Hai lần BFS, mỗi lần $O(n)$ vì mỗi đỉnh có tối đa hai cạnh.

Thêm đỉnh phụ cho trạng thái

Khi chi phí không nằm trên cạnh mà ở việc đổi một thứ gì đó (đổi tuyến, đổi màu, đổi phương tiện), thêm đỉnh mới cho thứ đó. Mỗi tuyến xe thành một đỉnh, nối với mọi ga trên tuyến: đi từ ga lên tuyến rồi xuống ga khác là hai cạnh, nên số tuyến đã dùng bằng nửa khoảng cách BFS. Số cạnh mới bằng số cặp (ga, tuyến), vẫn $O(m)$, trong khi nối thẳng mọi cặp ga cùng tuyến có thể tới $O(n^2)$ cạnh.

Ví dụÍt Tuyến Nhất Giữa Hai Ga

Đề. Mạng $n \le 2 \cdot 10^5$ ga, mỗi đường nối thuộc một tuyến có màu; các đường cùng màu liên thông với nhau. Tìm số tuyến ít nhất để đi từ ga $b$ tới ga $e$.

Lời giải. Số tuyến không phải số đường nối, nên BFS thẳng trên ga không đúng. Thêm một đỉnh cho mỗi tuyến và nối ga với tuyến chứa nó: đi từ ga lên tuyến, rồi từ tuyến xuống một ga khác, tốn 2 cạnh cho mỗi lần dùng một tuyến. Một tuyến liên thông nên lên ở bất kỳ ga nào của tuyến cũng tới được mọi ga của tuyến. Đường đi luôn xen kẽ ga, tuyến, ga, …, nên tới ga $e$ thì khoảng cách chẵn và số tuyến là d[e] / 2; $b = e$ thì bằng 0.

Bước 1: đỉnh tuyến. id[c] là chỉ số đỉnh của tuyến màu $c$, đánh từ $n + 1$ trở đi. Mỗi đường $(u, v, c)$ thêm hai cạnh ga với tuyến, không thêm cạnh ga với ga nào cả. Mảng cỡ $4 \cdot 10^5$ đủ cho $n$ ga và tối đa $m$ tuyến.

if (!id.count(c)) id[c] = ++k;
g[u].push_back(id[c]);
g[id[c]].push_back(u);
g[v].push_back(id[c]);
g[id[c]].push_back(v);

Bước 2: BFS thường từ ga $b$, rồi in d[e] / 2.

Bước 3: nhiều bộ test. Cuối mỗi bộ xóa danh sách kề của mọi đỉnh đã dùng, cả ga lẫn tuyến.

for (ll i = 1; i <= k; i++) g[i].clear();

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

const ll N = 4e5 + 5;
ll d[N];
vector<ll> g[N];

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

    ll T;
    cin >> T;
    while (T--) {
        ll n, m;
        cin >> n >> m;
        map<ll, ll> id;
        ll k = n;
        for (ll i = 1; i <= m; i++) {
            ll u, v, c;
            cin >> u >> v >> c;
            if (!id.count(c)) id[c] = ++k;
            g[u].push_back(id[c]);
            g[id[c]].push_back(u);
            g[v].push_back(id[c]);
            g[id[c]].push_back(v);
        }
        ll b, e;
        cin >> b >> e;
        for (ll i = 1; i <= k; i++) d[i] = -1;
        queue<ll> q;
        q.push(b);
        d[b] = 0;
        while (!q.empty()) {
            ll u = q.front();
            q.pop();
            for (ll v : g[u])
                if (d[v] == -1) {
                    d[v] = d[u] + 1;
                    q.push(v);
                }
        }
        cout << d[e] / 2 << '\n';
        for (ll i = 1; i <= k; i++) g[i].clear();
    }
}

Input1
6 5
1 2 7
2 3 7
3 4 8
4 5 8
5 6 9
1 6

Output3

$O((n + m) \log m)$, phần $\log$ do map nén màu.