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
đến5
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;
}