Bài tập.

Cho một đồ thị có hướng với n đỉnh, các đỉnh được đánh số từ 1 tới n. Hãy viết hàm kiểm tra xem có tồn tại đường đi từ đỉnh u tới đỉnh v (u khác v) hay không?

Các cạnh của đồ thị được biểu diễn dưới dạng mảng 2 chiều. Ví dụ:

e = [[1, 2], [2, 3]] có nghĩa là có cạnh nối giữa đỉnh 1 và đỉnh 2, đỉnh 2 và đỉnh 3.

Ví dụ

• Cho n = 3, e = [[1, 2], [2, 3]], u = 1, v = 3, output sẽ có dạng findPath(n, e, u, v) = true.
  Giải thích: đường đi từ đỉnh 1 tới đỉnh 3 có dạng: 1 -> 2 -> 3.
   
• Cho n = 4, e = [[1, 2], [3, 4], [2, 4]], u = 1, v = 3, output sẽ có dạng findPath(n, e, u, v) = false.
  Giải thích: Từ đỉnh 3 chỉ có cạnh đi ra chứ không có cạnh đi vào nên không có đỉnh nào có thể đi tới được đỉnh 3.

Hướng dẫn bài tập.

Bài này ta có thể làm nhiều cách, mình sẽ hướng dẫn các bạn làm theo cách tìm kiếm theo chiều sâu DFS.

Code mẫu:

Ngôn ngữ C++:

bool b[100001];
bool a[1001][1001];
bool kt = false;
void dfs(int u, int v, int n){
    b[u] = false;
    for (int i = 1; i <= n; i++){
        if (a[u][i] && b[i]){
            if (i == v){
                kt = true;
            }
            dfs(i, v, n);
            b[i] = true;
        }
    }
}
bool check(int n, std::vector<std::vector<int>> e, int u, int v)
{
    for (int i = 0; i <= n; i++){
        b[i] = true;
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            a[i][j] = false;
        }
    }
    for (int i = 0; i < e.size(); i++){
        a[e[i][0]][e[i][1]] = true;
    }
    dfs(u, v, n);
    return kt;
}