Bài 21: Đồ thị nhập môn trong C++ và Python: danh sách kề, BFS, DFS, thành phần liên thông và loang trên lưới

Series: Thuật toán cơ bản Độ khó: Trung bình Bài 21 / Thuật toán cơ bản Đồ thị BFS DFS

// Thuật toán cơ bản · Bài 21

Đồ thị nhập môn: cách lưu đồ thị, duyệt BFS, DFS, thành phần liên thông và loang trên lưới

Bản đồ giao thông, mạng bạn bè, mê cung, ván cờ… đều là đồ thị. Chỉ với hai thuật toán duyệt BFS và DFS, em đã giải được cả một lớp bài lớn trong đề thi.

Lời mở đầu

Các bài từ đầu series tới giờ đều làm việc trên mảng và xâu: dữ liệu xếp thành một hàng. Nhưng rất nhiều bài toán có dữ liệu dạng mạng lưới: các thành phố nối với nhau bằng đường, các bạn học sinh quen nhau, các ô của mê cung kề nhau. Mô hình toán học cho chúng là đồ thị (graph): một tập đỉnh và các cạnh nối các cặp đỉnh.

Bài này là bài nhập môn đồ thị: em học cách lưu một đồ thị trong chương trình và hai cách duyệt nó: BFS (duyệt theo chiều rộng, lan dần như vết dầu loang) và DFS (duyệt theo chiều sâu, đi tới tận cùng rồi mới quay lui). Đặc biệt, BFS tìm được đường đi ngắn nhất trên lưới, dạng bài “mê cung” rất hay gặp.

Bài 15Đệ quy và quay lui Bài 16Tìm kiếm nhị phân Bài 17Hai con trỏ, cửa sổ trượt Bài 18Thuật toán tham lam Bài 19Quy hoạch động nhập môn Bài 20Thao tác bit, bitmask Bài 21Đồ thị: BFS, DFS, loang Bài 22Kỹ năng luyện thi Bài 23Tổng ôn và đề thi thử

Trong bài này bạn sẽ học: các khái niệm đỉnh, cạnh, bậc, đường đi, liên thông; hai cách lưu đồ thị: ma trận kề và danh sách kề; thuật toán BFS với hàng đợi và cách tìm khoảng cách ngắn nhất; thuật toán DFS bằng đệ quy và đếm thành phần liên thông; kỹ thuật loang trên lưới với mảng hướng dx, dy. Có khung chạy tay BFS, DFS, mô phỏng loang trong mê cung và 8 bài tập kèm gợi ý.

Lộ trình bài viết, bấm vào từng phần để nhảy tới:

Phần 1Đồ thị là gì Phần 2Lưu đồ thị Phần 3BFS, đường ngắn nhất Phần 4DFS, liên thông Phần 5Loang trên lưới Bài tập8 bài + gợi ý

Phần 1Đồ thị là gì?

Một đồ thị gồm $n$ đỉnh (thường đánh số $1..n$) và $m$ cạnh, mỗi cạnh nối hai đỉnh. Đồ thị vô hướng khi cạnh đi được cả hai chiều (đường hai chiều, quan hệ bạn bè); có hướng khi cạnh chỉ đi một chiều (đường một chiều, quan hệ “theo dõi” trên mạng xã hội). Hai đỉnh có cạnh nối là kề nhau; số cạnh nối với một đỉnh là bậc của đỉnh đó. Một dãy đỉnh liên tiếp kề nhau là một đường đi. Các đỉnh đi tới được nhau tạo thành một thành phần liên thông.

Phần 2Lưu đồ thị: ma trận kề và danh sách kề

Đề bài thường cho đồ thị dưới dạng: dòng đầu $n$, $m$; $m$ dòng sau mỗi dòng hai số $u$, $v$ là một cạnh. Có hai cách lưu:

Ma trận kề a[u][v] = 1 nếu có cạnh $u$ – $v$. Kiểm tra hai đỉnh có kề nhau trong $O(1)$, nhưng tốn $n^2$ ô nhớ: chỉ dùng được khi $n \le$ khoảng 5000.
Danh sách kề vector<int> adj[N]: adj[u] chứa các đỉnh kề với $u$. Tốn $O(n + m)$ bộ nhớ, duyệt các đỉnh kề của $u$ nhanh. Đây là cách dùng mặc định khi thi.

Đọc đồ thị vô hướng vào danh sách kề

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

const int N = 100005;
vector<int> adj[N];                 // danh sách kề

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);        // đồ thị vô hướng: thêm cả hai chiều
    }
    for(int u = 1; u <= n; u++){
        cout << u << ":";
        for(int v : adj[u]) cout << " " << v;
        cout << "\n";
    }
    return 0;
}

n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)
for u in range(1, n + 1):
    print(f"{u}:", *adj[u])

Phần 3BFS: duyệt theo chiều rộng và đường đi ngắn nhất

BFS (Breadth-First Search) bắt đầu từ đỉnh $s$, thăm tất cả các đỉnh cách $s$ 1 cạnh, rồi tới các đỉnh cách 2 cạnh, rồi 3 cạnh… giống như ném hòn đá xuống mặt hồ, sóng lan ra từng vòng. Để thăm “theo từng vòng” ta dùng hàng đợi (queue, bài 11): lấy đỉnh ở đầu hàng ra, đưa các đỉnh kề chưa thăm vào cuối hàng.

Hệ quả quan trọng: khi một đỉnh được thăm lần đầu, số cạnh đã đi chính là khoảng cách ngắn nhất từ $s$ tới nó (với đồ thị không có trọng số). Ta lưu d[v] = d[u] + 1 khi đưa $v$ vào hàng đợi từ $u$; d[v] = -1 nghĩa là chưa thăm. Mỗi đỉnh vào hàng một lần, mỗi cạnh được xét hai lần: $O(n + m)$.

Code C++ và Python

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

vector<int> adj[100005];
int d[100005];

int main(){
    int n, m, s;
    cin >> n >> m >> s;
    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    for(int i = 1; i <= n; i++) d[i] = -1;
    queue<int> q;
    d[s] = 0; q.push(s);
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int v : adj[u]){
            if(d[v] == -1){
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
    for(int i = 1; i <= n; i++) cout << d[i] << " ";
    return 0;
}

from collections import deque
import sys
data = sys.stdin.read().split()
n, m, s = int(data[0]), int(data[1]), int(data[2])
adj = [[] for _ in range(n + 1)]
for i in range(m):
    u, v = int(data[3 + 2 * i]), int(data[4 + 2 * i])
    adj[u].append(v); adj[v].append(u)
d = [-1] * (n + 1)
d[s] = 0
q = deque([s])
while q:
    u = q.popleft()
    for v in adj[u]:
        if d[v] == -1:
            d[v] = d[u] + 1
            q.append(v)
print(*d[1:])

C++▶ Chạy tay từng dòng codeBFS từ đỉnh s: hàng đợi luôn chứa các đỉnh theo thứ tự khoảng cách tăng dần. d[v] = -1 nghĩa là chưa thăm.

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

4vector<int> adj[100005];

5int d[100005];

7int main(){

8 int n, m, s;

9 cin >> n >> m >> s;

10 for(int i = 0; i < m; i++){

11 int u, v; cin >> u >> v;

12 adj[u].push_back(v); adj[v].push_back(u);

13 }

14 for(int i = 1; i <= n; i++) d[i] = -1;

15 queue<int> q;

16 d[s] = 0; q.push(s);

17 while(!q.empty()){

18 int u = q.front(); q.pop();

19 for(int v : adj[u]){

20 if(d[v] == -1){

21 d[v] = d[u] + 1;

22 q.push(v);

23 }

24 }

25 }

26 for(int i = 1; i <= n; i++) cout << d[i] << " ";

27 return 0;

28}

Mô phỏng trực quan. Đọc code BFS thì chỉ thấy một hàng đợi và vòng while, khó hình dung vì sao nó cho ra đường đi ngắn nhất. Em bấm Tiếp để xem BFS loang ra từng lớp: đỉnh nào vào hàng đợi trước thì được xử lý trước, và nhãn d = … chính là khoảng cách tới đỉnh xuất phát:

MÔ PHỎNGBFS loang theo từng lớp trên đồ thịNhập số đỉnh (tối đa 10), các cạnh dạng u-v cách nhau dấu cách, và đỉnh xuất phát.

nCác cạnhXuất phát

đỉnh đang xét / cạnh đang xétđang nằm trong hàng đợiđã xử lý xong, cạnh cây BFSchưa thăm

Phần 4DFS: duyệt theo chiều sâu và thành phần liên thông

DFS (Depth-First Search) đi theo một hướng xa nhất có thể: từ đỉnh $u$ chọn một đỉnh kề chưa thăm, đi sang đó, rồi lại chọn tiếp… khi không còn đỉnh kề chưa thăm thì quay lui về đỉnh trước. Viết bằng đệ quy rất ngắn, đúng tinh thần quay lui ở bài 15.

DFS (hay BFS) từ một đỉnh thăm được đúng thành phần liên thông chứa đỉnh đó. Muốn đếm số thành phần: duyệt các đỉnh $1..n$, gặp đỉnh nào chưa thăm thì tăng bộ đếm và DFS từ nó để đánh dấu cả thành phần.

Code C++ và Python

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

vector<int> adj[100005];
bool tham[100005];

void dfs(int u){
    tham[u] = true;
    for(int v : adj[u])
        if(!tham[v]) dfs(v);
}

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    int dem = 0;
    for(int u = 1; u <= n; u++){
        if(!tham[u]){
            dem++;
            dfs(u);
        }
    }
    cout << dem;
    return 0;
}

import sys
sys.setrecursionlimit(300000)
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
for i in range(m):
    u, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])
    adj[u].append(v); adj[v].append(u)
tham = [False] * (n + 1)

def dfs(u):
    tham[u] = True
    for v in adj[u]:
        if not tham[v]:
            dfs(v)

dem = 0
for u in range(1, n + 1):
    if not tham[u]:
        dem += 1
        dfs(u)
print(dem)

C++▶ Chạy tay từng dòng codeĐếm thành phần liên thông: mỗi lần gặp đỉnh chưa thăm là một thành phần mới, DFS từ đó tô màu cả thành phần. Để ý ngăn xếp đệ quy dài ra rồi co lại.

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

4vector<int> adj[100005];

5bool tham[100005];

7void dfs(int u){

8 tham[u] = true;

9 for(int v : adj[u])

10 if(!tham[v]) dfs(v);

11}

13int main(){

14 int n, m;

15 cin >> n >> m;

16 for(int i = 0; i < m; i++){

17 int u, v; cin >> u >> v;

18 adj[u].push_back(v); adj[v].push_back(u);

19 }

20 int dem = 0;

21 for(int u = 1; u <= n; u++){

22 if(!tham[u]){

23 dem++;

24 dfs(u);

25 }

26 }

27 cout << dem;

28 return 0;

29}

BFS hay DFS?

Cả hai đều $O(n + m)$ và đều tìm được thành phần liên thông, kiểm tra hai đỉnh có đường đi tới nhau. Cần đường đi ngắn nhất (ít cạnh nhất) thì bắt buộc dùng BFS; DFS tìm được một đường đi nhưng không chắc ngắn nhất. DFS đệ quy viết ngắn hơn nhưng với $n \approx 10^6$ có thể tràn ngăn xếp (nhất là Python); khi đó dùng BFS hoặc DFS bằng ngăn xếp tự quản lý.

Mô phỏng trực quan. DFS đệ quy “đi sâu rồi quay lui” nghe thì dễ, nhưng máy nhớ đường quay về bằng cách nào? Bằng ngăn xếp lời gọi hàm. Em hãy theo dõi ngăn xếp đó bên dưới đồ thị, đồng thời xem vòng lặp ngoài đếm từng thành phần liên thông:

MÔ PHỎNGDFS đệ quy và ngăn xếp lời gọi khi đếm thành phần liên thôngNhập số đỉnh (tối đa 10) và các cạnh dạng u-v. Đồ thị có thể gồm nhiều mảnh rời nhau.

nCác cạnh

lời gọi đang chạyđang dang dở trên ngăn xếpđã quay lui xong, cạnh đi xuốngchưa thăm

Phần 5Loang trên lưới: mê cung và đếm vùng

Lưới ô vuông là một đồ thị “ngầm”: mỗi ô là một đỉnh, hai ô chung cạnh là kề nhau. Ta không cần tạo danh sách kề, chỉ cần mảng hướng:

int dx[4] = {-1, 1, 0, 0};    // lên, xuống, trái, phải
int dy[4] = {0, 0, -1, 1};
for(int k = 0; k < 4; k++){
    int x = u.first + dx[k], y = u.second + dy[k];
    if(x < 0 || x >= m || y < 0 || y >= n) continue;   // ra ngoài lưới
    if(g[x][y] == '#' || d[x][y] != -1) continue;       // tường hoặc đã thăm
    d[x][y] = d[u.first][u.second] + 1;
    q.push({x, y});
}

BFS từ ô xuất phát cho khoảng cách ngắn nhất tới mọi ô; đi ngược theo các ô có khoảng cách giảm dần 1 sẽ ra đường đi. Muốn đếm số “vùng” (hòn đảo, căn phòng…) thì làm như đếm thành phần liên thông. Thêm 4 hướng chéo vào dx, dy thì thành lưới 8 hướng; đổi thành 8 bước nhảy của quân mã thì giải bài quân mã.

Đường đi ngắn nhất trong mê cung bằng BFS

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

int m, n, d[1005][1005];
string g[1005];
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

int main(){
    cin >> m >> n;
    int sx = 0, sy = 0, ex = 0, ey = 0;
    for(int i = 0; i < m; i++){
        cin >> g[i];
        for(int j = 0; j < n; j++){
            if(g[i][j] == 'S'){ sx = i; sy = j; }
            if(g[i][j] == 'E'){ ex = i; ey = j; }
            d[i][j] = -1;
        }
    }
    queue<pair<int,int>> q;
    d[sx][sy] = 0; q.push({sx, sy});
    while(!q.empty()){
        auto [x, y] = q.front(); q.pop();
        for(int k = 0; k < 4; k++){
            int u = x + dx[k], v = y + dy[k];
            if(u < 0 || u >= m || v < 0 || v >= n) continue;
            if(g[u][v] == '#' || d[u][v] != -1) continue;
            d[u][v] = d[x][y] + 1;
            q.push({u, v});
        }
    }
    cout << d[ex][ey];          // -1 nếu không tới được
    return 0;
}

from collections import deque
m, n = map(int, input().split())
g = [input().strip() for _ in range(m)]
d = [[-1] * n for _ in range(m)]
for i in range(m):
    for j in range(n):
        if g[i][j] == 'S': sx, sy = i, j
        if g[i][j] == 'E': ex, ey = i, j
d[sx][sy] = 0
q = deque([(sx, sy)])
while q:
    x, y = q.popleft()
    for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        u, v = x + dx, y + dy
        if 0 <= u < m and 0 <= v < n and g[u][v] != '#' and d[u][v] == -1:
            d[u][v] = d[x][y] + 1
            q.append((u, v))
print(d[ex][ey])

Xem “vết dầu loang” trong mê cung: bấm vào một ô để đặt hoặc xóa tường, rồi bấm Tự chạy. Màu càng đậm là càng xa ô xuất phát S; khi chạm tới E, đường đi ngắn nhất được tô sáng. Thử chuyển sang DFS để thấy DFS đi “lung tung” và không cho đường ngắn nhất.

MÔ PHỎNGBFS và DFS loang trong mê cungBấm vào ô để đặt/xóa tường. S là ô xuất phát (góc trái trên), E là đích (góc phải dưới).

Đang tải mô phỏng…

Luyện tập trên web

Các bài dưới đây trên blog đều có lời giải chi tiết bằng C++ và Python, xếp từ dễ tới khó. Em hãy tự làm trước rồi mới xem lời giải nhé.

Covid (ICTU P58) (Trung bình)
Lá Bài (LABAI) (Trung bình)
The Time When the Network Becomes Idle (LeetCode 2039) (Trung bình)
Nhà Từ Thiện Swyrin (Trung bình)
Số Cách Đi Quân Mã (SOCACH) (Khá)

Xem toàn bộ bài cùng chủ đề: nhãn BFS.

Bài tậpLuyện đồ thị

Bài 1Bậc của đỉnhDễ

Cho đồ thị vô hướng $n$ đỉnh, $m$ cạnh ($n, m \le 10^5$). In bậc của các đỉnh $1..n$.

Input

Output

2 2 3 1

💡 Gợi ý

Không cần lưu cả đồ thị: mỗi cạnh $(u, v)$ làm bậc của $u$ và $v$ cùng tăng 1. (Tổng các bậc luôn bằng $2m$.)

Xem code tham khảo (C++ / Python)

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

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> deg(n + 1, 0);
    for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; deg[u]++; deg[v]++; }
    for(int u = 1; u <= n; u++) cout << deg[u] << (u < n ? " " : "\n");
    return 0;
}

import sys
data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
deg = [0] * (n + 1)
for i in range(m):
    deg[data[2 + 2 * i]] += 1
    deg[data[3 + 2 * i]] += 1
print(*deg[1:])

Bài 2Có đường đi không?Dễ

Cho đồ thị vô hướng $n$ đỉnh, $m$ cạnh và hai đỉnh $s$, $t$. In YES nếu có đường đi từ $s$ tới $t$, ngược lại NO.

Input

Output

NO

💡 Gợi ý

BFS hoặc DFS từ $s$, kiểm tra $t$ có được thăm không.

Xem code tham khảo (C++ / Python)

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

int main(){
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    vector<vector<int>> adj(n + 1);
    for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); }
    vector<bool> tham(n + 1, false);
    queue<int> q; q.push(s); tham[s] = true;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int v : adj[u]) if(!tham[v]){ tham[v] = true; q.push(v); }
    }
    cout << (tham[t] ? "YES" : "NO");
    return 0;
}

from collections import deque
import sys
data = list(map(int, sys.stdin.read().split()))
n, m, s, t = data[:4]
adj = [[] for _ in range(n + 1)]
for i in range(m):
    u, v = data[4 + 2 * i], data[5 + 2 * i]
    adj[u].append(v); adj[v].append(u)
tham = [False] * (n + 1)
tham[s] = True
q = deque([s])
while q:
    u = q.popleft()
    for v in adj[u]:
        if not tham[v]:
            tham[v] = True
            q.append(v)
print("YES" if tham[t] else "NO")

Bài 3Số nhóm bạnDễ

Lớp có $n$ học sinh và $m$ cặp bạn thân ($n, m \le 10^5$). Bạn của bạn cũng là cùng nhóm. Lớp có bao nhiêu nhóm bạn? (Học sinh không có bạn nào tự tạo một nhóm.)

Input

Output

💡 Gợi ý

Đếm thành phần liên thông như phần 4. Dùng BFS cho an toàn với $n$ lớn. Ba nhóm: {1, 2, 3}, {4}, {5, 6}.

Xem code tham khảo (C++ / Python)

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

int main(){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); }
    vector<bool> tham(n + 1, false);
    int dem = 0;
    for(int s = 1; s <= n; s++){
        if(tham[s]) continue;
        dem++;
        queue<int> q; q.push(s); tham[s] = true;
        while(!q.empty()){
            int u = q.front(); q.pop();
            for(int v : adj[u]) if(!tham[v]){ tham[v] = true; q.push(v); }
        }
    }
    cout << dem;
    return 0;
}

from collections import deque
import sys
data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
adj = [[] for _ in range(n + 1)]
for i in range(m):
    u, v = data[2 + 2 * i], data[3 + 2 * i]
    adj[u].append(v); adj[v].append(u)
tham = [False] * (n + 1)
dem = 0
for s in range(1, n + 1):
    if tham[s]:
        continue
    dem += 1
    tham[s] = True
    q = deque([s])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if not tham[v]:
                tham[v] = True
                q.append(v)
print(dem)

Bài 4Khoảng cách từ thủ đôTrung bình

Đất nước có $n$ thành phố, $m$ con đường hai chiều ($n, m \le 10^5$). Thủ đô là thành phố 1. In số con đường ít nhất phải đi từ thủ đô tới từng thành phố $1..n$ ($-1$ nếu không tới được).

Input

Output

0 1 1 2 3 -1

💡 Gợi ý

Đúng chương trình BFS ở phần 3 với $s = 1$.

Xem code tham khảo (C++ / Python)

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

int main(){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); }
    vector<int> d(n + 1, -1);
    queue<int> q; q.push(1); d[1] = 0;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int v : adj[u]) if(d[v] == -1){ d[v] = d[u] + 1; q.push(v); }
    }
    for(int i = 1; i <= n; i++) cout << d[i] << (i < n ? " " : "\n");
    return 0;
}

from collections import deque
import sys
data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
adj = [[] for _ in range(n + 1)]
for i in range(m):
    u, v = data[2 + 2 * i], data[3 + 2 * i]
    adj[u].append(v); adj[v].append(u)
d = [-1] * (n + 1)
d[1] = 0
q = deque([1])
while q:
    u = q.popleft()
    for v in adj[u]:
        if d[v] == -1:
            d[v] = d[u] + 1
            q.append(v)
print(*d[1:])

Bài 5Đếm số hòn đảoTrung bình

Bản đồ $m \times n$ ($m, n \le 1000$), # là đất, . là nước. Các ô đất chung cạnh thuộc cùng một hòn đảo. Đếm số hòn đảo.

Input

4 5
##..#
#...#
..#..
.....

Output

💡 Gợi ý

Duyệt mọi ô; gặp ô đất chưa thăm thì tăng bộ đếm và loang BFS (4 hướng) để đánh dấu cả hòn đảo.

Xem code tham khảo (C++ / Python)

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

int main(){
    int m, n;
    cin >> m >> n;
    vector<string> g(m);
    for(auto &s : g) cin >> s;
    vector<vector<bool>> tham(m, vector<bool>(n, false));
    int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}, dem = 0;
    for(int i = 0; i < m; i++)
        for(int j = 0; j < n; j++){
            if(g[i][j] != '#' || tham[i][j]) continue;
            dem++;
            queue<pair<int,int>> q; q.push({i, j}); tham[i][j] = true;
            while(!q.empty()){
                auto [x, y] = q.front(); q.pop();
                for(int k = 0; k < 4; k++){
                    int u = x + dx[k], v = y + dy[k];
                    if(u >= 0 && u < m && v >= 0 && v < n && g[u][v] == '#' && !tham[u][v]){
                        tham[u][v] = true; q.push({u, v});
                    }
                }
            }
        }
    cout << dem;
    return 0;
}

from collections import deque
m, n = map(int, input().split())
g = [input().strip() for _ in range(m)]
tham = [[False] * n for _ in range(m)]
dem = 0
for i in range(m):
    for j in range(n):
        if g[i][j] != '#' or tham[i][j]:
            continue
        dem += 1
        tham[i][j] = True
        q = deque([(i, j)])
        while q:
            x, y = q.popleft()
            for u, v in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
                if 0 <= u < m and 0 <= v < n and g[u][v] == '#' and not tham[u][v]:
                    tham[u][v] = True
                    q.append((u, v))
print(dem)

Bài 6Thoát khỏi mê cungTrung bình

Mê cung $m \times n$ ($m, n \le 1000$) gồm . (đường), # (tường), một ô S và một ô E. Mỗi bước đi sang ô chung cạnh. In số bước ít nhất từ S tới E, hoặc $-1$.

Input

4 5
S.#..
.##.#
...#E
#....

Output

💡 Gợi ý

Chương trình BFS trên lưới ở phần 5. Chú ý ô E và S cũng đi được (chỉ chặn #).

Xem code tham khảo (C++ / Python)

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

int main(){
    int m, n;
    cin >> m >> n;
    vector<string> g(m);
    for(auto &s : g) cin >> s;
    vector<vector<int>> d(m, vector<int>(n, -1));
    int sx = 0, sy = 0, ex = 0, ey = 0;
    for(int i = 0; i < m; i++) for(int j = 0; j < n; j++){
        if(g[i][j] == 'S'){ sx = i; sy = j; }
        if(g[i][j] == 'E'){ ex = i; ey = j; }
    }
    int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
    queue<pair<int,int>> q; q.push({sx, sy}); d[sx][sy] = 0;
    while(!q.empty()){
        auto [x, y] = q.front(); q.pop();
        for(int k = 0; k < 4; k++){
            int u = x + dx[k], v = y + dy[k];
            if(u >= 0 && u < m && v >= 0 && v < n && g[u][v] != '#' && d[u][v] == -1){
                d[u][v] = d[x][y] + 1; q.push({u, v});
            }
        }
    }
    cout << d[ex][ey];
    return 0;
}

from collections import deque
m, n = map(int, input().split())
g = [input().strip() for _ in range(m)]
for i in range(m):
    for j in range(n):
        if g[i][j] == 'S': sx, sy = i, j
        if g[i][j] == 'E': ex, ey = i, j
d = [[-1] * n for _ in range(m)]
d[sx][sy] = 0
q = deque([(sx, sy)])
while q:
    x, y = q.popleft()
    for u, v in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
        if 0 <= u < m and 0 <= v < n and g[u][v] != '#' and d[u][v] == -1:
            d[u][v] = d[x][y] + 1
            q.append((u, v))
print(d[ex][ey])

Bài 7Quân mãTrung bình

Bàn cờ $n \times n$ ($n \le 1000$). Quân mã ở ô $(x_1, y_1)$, mỗi bước đi theo hình chữ L (8 kiểu). Cần ít nhất bao nhiêu bước để tới ô $(x_2, y_2)$? (Tọa độ từ 1.)

Input

8
1 1 8 8

Output

💡 Gợi ý

BFS trên lưới với 8 hướng nhảy của quân mã thay cho 4 hướng: dx = {1, 2, 2, 1, -1, -2, -2, -1}, dy = {2, 1, -1, -2, -2, -1, 1, 2}.

Xem code tham khảo (C++ / Python)

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

int main(){
    int n, x1, y1, x2, y2;
    cin >> n >> x1 >> y1 >> x2 >> y2;
    vector<vector<int>> d(n + 1, vector<int>(n + 1, -1));
    int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1}, dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};
    queue<pair<int,int>> q; q.push({x1, y1}); d[x1][y1] = 0;
    while(!q.empty()){
        auto [x, y] = q.front(); q.pop();
        for(int k = 0; k < 8; k++){
            int u = x + dx[k], v = y + dy[k];
            if(u >= 1 && u <= n && v >= 1 && v <= n && d[u][v] == -1){
                d[u][v] = d[x][y] + 1; q.push({u, v});
            }
        }
    }
    cout << d[x2][y2];
    return 0;
}

from collections import deque
n = int(input())
x1, y1, x2, y2 = map(int, input().split())
d = [[-1] * (n + 1) for _ in range(n + 1)]
d[x1][y1] = 0
q = deque([(x1, y1)])
moves = ((1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2))
while q:
    x, y = q.popleft()
    for a, b in moves:
        u, v = x + a, y + b
        if 1 <= u <= n and 1 <= v <= n and d[u][v] == -1:
            d[u][v] = d[x][y] + 1
            q.append((u, v))
print(d[x2][y2])

Bài 8Đám cháyKhá

Khu rừng $m \times n$ ($m, n \le 1000$): F là ô đang cháy, T là cây, . là đất trống. Mỗi phút lửa lan từ ô cháy sang các ô cây chung cạnh. Sau bao nhiêu phút mọi cây đều cháy? Nếu có cây không bao giờ cháy, in $-1$.

Input

3 4
FTT.
.T.T
TTTF

Output

💡 Gợi ý

BFS đa nguồn: đưa tất cả ô F vào hàng đợi ngay từ đầu với khoảng cách 0, rồi BFS bình thường chỉ đi vào ô T. Đáp án là khoảng cách lớn nhất; nếu còn ô T chưa thăm thì in $-1$. Lửa từ nhiều nơi lan đồng thời, đúng như BFS lan theo từng vòng.

Xem code tham khảo (C++ / Python)

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

int main(){
    int m, n;
    cin >> m >> n;
    vector<string> g(m);
    for(auto &s : g) cin >> s;
    vector<vector<int>> d(m, vector<int>(n, -1));
    queue<pair<int,int>> q;
    for(int i = 0; i < m; i++) for(int j = 0; j < n; j++)
        if(g[i][j] == 'F'){ d[i][j] = 0; q.push({i, j}); }
    int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}, kq = 0;
    while(!q.empty()){
        auto [x, y] = q.front(); q.pop();
        kq = max(kq, d[x][y]);
        for(int k = 0; k < 4; k++){
            int u = x + dx[k], v = y + dy[k];
            if(u >= 0 && u < m && v >= 0 && v < n && g[u][v] == 'T' && d[u][v] == -1){
                d[u][v] = d[x][y] + 1; q.push({u, v});
            }
        }
    }
    for(int i = 0; i < m; i++) for(int j = 0; j < n; j++)
        if(g[i][j] == 'T' && d[i][j] == -1){ cout << -1; return 0; }
    cout << kq;
    return 0;
}

from collections import deque
m, n = map(int, input().split())
g = [input().strip() for _ in range(m)]
d = [[-1] * n for _ in range(m)]
q = deque()
for i in range(m):
    for j in range(n):
        if g[i][j] == 'F':
            d[i][j] = 0
            q.append((i, j))
kq = 0
while q:
    x, y = q.popleft()
    kq = max(kq, d[x][y])
    for u, v in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
        if 0 <= u < m and 0 <= v < n and g[u][v] == 'T' and d[u][v] == -1:
            d[u][v] = d[x][y] + 1
            q.append((u, v))
if any(g[i][j] == 'T' and d[i][j] == -1 for i in range(m) for j in range(n)):
    print(-1)
else:
    print(kq)

Bài tiếp theo · Bài 22

Kỹ năng luyện thi: debug, sinh test, chấm trâu

Những kỹ năng ít ai dạy bài bản nhưng giúp lên điểm rõ rệt: tìm lỗi nhanh, tự sinh test, viết lời giải “trâu” để đối chiếu và đọc giới hạn đề.

Học bài 22 →

← Bài 20: Thao tác bit Xem cả series Thuật toán cơ bản

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇

Bản quyền thuộc về Thầy Nguyễn Việt Nam Sơn. Bài viết, lời giải, hình minh hoạ và mã nguồn trên trang là công sức biên soạn của thầy qua nhiều năm giảng dạy. Vui lòng không sao chép, đăng lại hay sử dụng dưới mọi hình thức khi chưa được sự đồng ý của tác giả. Nếu thấy hữu ích, hãy chia sẻ bằng đường link bài gốc nhé. Cảm ơn bạn!

Lập Trình Thuật Toán

Bài 21: Đồ thị nhập môn trong C++ và Python: danh sách kề, BFS, DFS, thành phần liên thông và loang trên lưới

Lời mở đầu

Phần 1Đồ thị là gì?

Phần 2Lưu đồ thị: ma trận kề và danh sách kề

Phần 3BFS: duyệt theo chiều rộng và đường đi ngắn nhất

Phần 4DFS: duyệt theo chiều sâu và thành phần liên thông

Phần 5Loang trên lưới: mê cung và đếm vùng

Bài tậpLuyện đồ thị

Nhận xét

Đăng nhận xét

Dữ liệu trang web (tự động – không xoá)

Hướng dẫn tham gia Thi thử HSG Tin học hàng tuần trên ClueOJ (từ đăng ký tài khoản đến lúc vào phòng thi)

Khóa học luyện thi chuyên Tin, HSG Tin học – lập trình thuật toán C++