DFS — duyệt theo chiều sâu

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size(), m = grid[0].size(), dao = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (grid[i][j] == '1') {
                    dao++;          // tìm thấy một đảo mới
                    dfs(grid, i, j);  // xoá sạch cả đảo đó
                }
        return dao;
    }

private:
    void dfs(vector<vector<char>>& grid, int r, int c) {
        int n = grid.size(), m = grid[0].size();
        if (r < 0 || c < 0 || r >= n || c >= m) return;  // ra ngoài lưới
        if (grid[r][c] != '1') return;                   // nước, hoặc đã thăm
        grid[r][c] = '0';                                // đánh dấu đã thăm NGAY
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }
};

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        n, m = len(grid), len(grid[0])

        def dfs(r: int, c: int) -> None:
            if r < 0 or c < 0 or r >= n or c >= m:   # ra ngoài lưới
                return
            if grid[r][c] != '1':                    # nước, hoặc đã thăm
                return
            grid[r][c] = '0'                         # đánh dấu đã thăm NGAY
            dfs(r - 1, c)
            dfs(r + 1, c)
            dfs(r, c - 1)
            dfs(r, c + 1)

        dao = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == '1':
                    dao += 1        # tìm thấy một đảo mới
                    dfs(i, j)       # xoá sạch cả đảo đó
        return dao

class Solution {
public:
    int findCircleNum(vector<vector<int>>& keNhau) {
        int n = keNhau.size(), soTinh = 0;
        vector<bool> daTham(n, false);
        for (int u = 0; u < n; u++)
            if (!daTham[u]) {
                soTinh++;                    // một tỉnh mới
                dfs(keNhau, daTham, u);
            }
        return soTinh;
    }

private:
    void dfs(vector<vector<int>>& keNhau, vector<bool>& daTham, int u) {
        daTham[u] = true;                    // đánh dấu NGAY khi bước vào
        int n = keNhau.size();
        for (int v = 0; v < n; v++)
            if (keNhau[u][v] == 1 && !daTham[v])
                dfs(keNhau, daTham, v);
    }
};

class Solution:
    def findCircleNum(self, keNhau: List[List[int]]) -> int:
        n = len(keNhau)
        daTham = [False] * n

        def dfs(u: int) -> None:
            daTham[u] = True                 # đánh dấu NGAY khi bước vào
            for v in range(n):
                if keNhau[u][v] == 1 and not daTham[v]:
                    dfs(v)

        soTinh = 0
        for u in range(n):
            if not daTham[u]:
                soTinh += 1                  # một tỉnh mới
                dfs(u)
        return soTinh

class Solution {
public:
    bool canFinish(int n, vector<vector<int>>& dieuKien) {
        vector<vector<int>> ke(n);
        for (auto& p : dieuKien)
            ke[p[1]].push_back(p[0]);        // học p[1] xong mới học được p[0]

        // 0 = trắng (chưa xét), 1 = xám (đang trong đường đi), 2 = đen (đã xong)
        vector<int> mau(n, 0);
        for (int u = 0; u < n; u++)
            if (mau[u] == 0 && coChuTrinh(ke, mau, u))
                return false;
        return true;
    }

private:
    bool coChuTrinh(vector<vector<int>>& ke, vector<int>& mau, int u) {
        mau[u] = 1;                          // bước vào: tô xám
        for (int v : ke[u]) {
            if (mau[v] == 1) return true;    // gặp lại đỉnh xám → CHU TRÌNH
            if (mau[v] == 0 && coChuTrinh(ke, mau, v)) return true;
            // mau[v] == 2: đã xét xong nhánh đó, bỏ qua
        }
        mau[u] = 2;                          // đi ra: tô đen
        return false;
    }
};

class Solution:
    def canFinish(self, n: int, dieuKien: List[List[int]]) -> bool:
        ke = [[] for _ in range(n)]
        for sau, truoc in dieuKien:
            ke[truoc].append(sau)            # học truoc xong mới học được sau

        # 0 = trắng (chưa xét), 1 = xám (đang trong đường đi), 2 = đen (đã xong)
        mau = [0] * n

        def coChuTrinh(u: int) -> bool:
            mau[u] = 1                       # bước vào: tô xám
            for v in ke[u]:
                if mau[v] == 1:              # gặp lại đỉnh xám → CHU TRÌNH
                    return True
                if mau[v] == 0 and coChuTrinh(v):
                    return True
                # mau[v] == 2: đã xét xong nhánh đó, bỏ qua
            mau[u] = 2                       # đi ra: tô đen
            return False

        for u in range(n):
            if mau[u] == 0 and coChuTrinh(u):
                return False
        return True