CTDL và giải thuật - Bài tập 3

Bài tập.

Có n thành phố được đánh số từ 1 đến  n. Cho ma trận a thể hiện tính liên thông giữa các thành phố, ví dụ a = [[1, 2], [3, 4]] có nghĩa là:

  • Thành phố 1 và 2 có thể đi đến với nhau với quãng đường là 1.
  • Thành phố 3 và 4 cũng tương tự.

Cho hai số u và v phân biệt. Hãy đưa ra quãng đường daif nhất để đi từ thành phố u đến thành phố v, với điều kiện mỗi thành phố chỉ đi qua một lần . Trả về -1 nếu từ thành phố u không thể đi đến thành phố v.

Ví dụ:

  • Với n = 6, e = [[1,3], [1,2], [2, 3], [3,4], [2,5], [4,6], [6,5], [4,5]], u = 1, v = 5 thì graphFunction(n, e, u, v) = 4.

    Có nhiều cách di chuyển từ thành phố 1 đến 5 những cách đi dài thõa mãn đó là 1 -> 3 -> 4 -> 6 -> 5 với quãng đường là 2.
     
  • Với n = 2, e = [[1,2], [3,4]], u = 2, v = 3 thì graphFunction(n, e, u, v) = -1.

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

Code mẫu:

bool b[100001];
bool a[1001][1001];
int M = -1;
void dfs(int u, int v, int n, int count){
    b[u] = false;
    for (int i = 1; i <= n; i++){
        if (a[u][i] && b[i]){
            if (i == v){
                if (count+1 > M){
                    M = count+1;
                    break;
                }
            }
            dfs(i, v, n, count+1);
            b[i] = true;
        }
    }
}
int graphFunction(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;
        a[e[i][1]][e[i][0]] = true;
    }
    dfs(u, v, n, 0);
    return M;
}