Cho đồ thị vô hướng và không có trọng số làm đầu vào, nhiệm vụ là tìm tích các chu trình được hình thành trong đồ thị cho trước và hiển thị kết quả.
Ví dụ
Đầu vào
Trong hình cho, có 8 nút và trong đó 5 nút tạo thành chu trình bao gồm 1, 6, 3, 5, 8 và các nút còn lại không nằm trong chu trình. Do đó, độ dài chu trình là 5 vì bao gồm 5 nút, nên tích là 5.
Trong hình cho, có 12 nút và trong đó 11 (5 + 6) nút tạo thành chu trình bao gồm 1, 6, 3, 5, 8 và 9, 4, 10, 11, 22, 12 và nút còn lại là 2 không nằm trong chu trình. Vậy độ dài chu trình là 5 * 6 = 30.
Cách tiếp cận dùng trong chương trình dưới đây –
- Nhập các nút tạo thành chu trình
- Tạo hàm DFS và gọi nó để duyệt đỉnh bằng cách tô màu
- Nút được đánh dấu đã duyệt hoàn toàn hoặc một phần
- Nút đã duyệt hoàn toàn không cần duyệt lại và do đó không cần lưu trữ, trong khi nút duyệt một phần cần lưu trữ vì chúng được duyệt lại
- In kết quả
Thuật toán
Bắt đầu
Bước 1 -> Khai báo hàm duyệt đồ thị dùng DFS
void DFS(int i, int j, int color[], int highlight[], int parent[], int& number)
NẾU color[i] = 2
Trả về
Kết thúc
NẾU color[i] = 1
Gán number++
Khai báo và gán int temp = j
Gán highlight[temp] = number
Vòng lặp Khi temp != i
Gán temp = parent[temp]
Gán highlight[temp] = number
Kết thúc
Trả về
Kết thúc
Gán parent[i] = j
Gán color[i] = 1
Với int k : graph[i]
NẾU k = parent[i]
Tiếp tục
Kết thúc
Gọi DFS(k, i, color, highlight, parent, number)
Kết thúc
Gán color[i] = 2
Bước 2 -> Khai báo hàm tìm tích các nút trong chu trình
int product(int edge, int highlight[], int& number)
gọi unordered_map<int, int> mp
Vòng lặp Với i = 1 đến i <= edge và i++
NẾU (highlight[i] != 0)
Gán mp[highlight[i]]++
Kết thúc
Kết thúc
Khai báo và gán int temp = 1
Vòng lặp Với i = 1 đến i <= number và i++
Gán temp = temp * mp[i]
Kết thúc
NẾU number = 0
Gán temp = 0
Kết thúc
trả về temp
Bước 3 -> Trong main()
Gọi hàm insert(1, 2) để chèn nút
Khai báo int color[size], parent[size]
Khai báo int highlight[size]
Khai báo và gán int number = 0
Khai báo và gán int edge = 10
Gọi DFS(1, 0, color, highlight, parent, number)
Gọi hàm in product(edge, highlight, number)
Kết thúc
Ví dụ mã C++
#include <bits/stdc++.h>
using namespace std;
const int size = 100000;
vector<int> graph[size];
// Hàm duyệt đồ thị dùng DFS
void DFS(int i, int j, int color[], int highlight[], int parent[], int& number) {
// cho nút đã duyệt
if (color[i] == 2) {
return;
}
// chưa duyệt hoàn toàn
if (color[i] == 1) {
number++;
int temp = j;
highlight[temp] = number;
// backtracking đỉnh
while (temp != i) {
temp = parent[temp];
highlight[temp] = number;
}
return;
}
parent[i] = j;
color[i] = 1;
for (int k : graph[i]) {
if (k == parent[i]) {
continue;
}
DFS(k, i, color, highlight, parent, number);
}
color[i] = 2;
}
// Hàm chèn cạnh vào đồ thị
void insert(int u, int v) {
graph[u].push_back(v);
graph[v].push_back(u);
}
// Tìm tích các nút trong chu trình
int product(int edge, int highlight[], int& number) {
unordered_map<int, int> mp;
for (int i = 1; i <= edge; i++) {
if (highlight[i] != 0)
mp[highlight[i]]++;
}
int temp = 1;
for (int i = 1; i <= number; i++) {
temp = temp * mp[i];
}
if (number == 0)
temp = 0;
return temp;
}
int main() {
// chèn nút vào đồ thị
insert(1, 2);
insert(2, 3);
insert(3, 4);
insert(4, 6);
insert(4, 7);
insert(5, 6);
insert(3, 5);
insert(7, 8);
insert(6, 10);
insert(5, 9);
insert(10, 11);
int color[size], parent[size];
int highlight[size];
int number = 0;
int edge = 10;
DFS(1, 0, color, highlight, parent, number);
// hàm in các chu trình
cout << "tích tất cả các nút trong chu trình là: " << product(edge, highlight, number);
return 0;
}
Đầu ra
Tích tất cả các nút trong chu trình là: 4