Từ những bài viết đầu tiên về chuyên đề Lý thuyết đồ thị, tôi đã giới thiệu tới các bạn khái niệm về Chu trình trên đồ thị. Một đường đi {v0,v1,v2,…,vk}{v_0, v_1, v_2, dots, v_k}{v0,v1,v2,…,vk} trên đồ thị được gọi là một chu trình nếu như v0=vk,v_0 = v_k,v0=vk, và nếu như các cạnh trên đường đi đó đều phân biệt. Ngoài ra, trên đồ thị còn có thể tồn tại hai dạng chu trình đặc biệt là Chu trình Euler và Chu trình Hamilton, sẽ được đề cập tới ở những bài viết tiếp theo.
Trong bài viết này, chúng ta sẽ cùng nhau đi sâu hơn vào cách xác định chu trình trên đồ thị và những bài toán ứng dụng của nó.
Giải thuật DFStext{DFS}DFS là một công cụ rất hữu hiệu để xác định chu trình trên đồ thị. Sau đây, chúng ta sẽ cùng tìm hiểu về ý tưởng của giải thuật.
1. Phát biểu bài toán
Cho một đơn đồ thị vô hướng GGG gồm nnn đỉnh và mmm cung (có thể có “khuyên” – cạnh tự nối một đỉnh với chính nó). Các đỉnh của đồ thị được đánh số từ 111 tới nnn.
Một chu trình trên đồ thị là một đường đi (x1,x2,…,xk,x1)(x_1, x_2, dots, x_k, x_1)(x1,x2,…,xk,x1) với hai đỉnh đầu và cuối của đường đi giống nhau.
Hãy xác định đồ thị trên có chứa chu trình nào hay không?
Input:
- Dòng đầu tiên chứa hai số nguyên nnn và mmm – số đỉnh và số cạnh của đồ thị (1≤n,m≤105)(1 le n, m le 10^5)(1≤n,m≤105).
- mmm dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u,vu, vu,v – thể hiện một cạnh của đồ thị nối hai đỉnh uuu và vvv.
Output:
- In ra YES nếu đồ thị có chứa chu trình, ngược lại in ra NO.
Sample Input 1:
4 4 1 2 2 3 3 4 4 2
Sample Output 1:
YES
Sample Input 2:
4 3 1 2 1 3 4 3
Sample Output 2:
NO
2. Ý tưởng
Phân loại các cung trên cây DFS
Trong quá trình duyệt DFStext{DFS}DFS trên đồ thị, nếu như ta chỉ giữ lại các cạnh (u,v)(u, v)(u,v) với uuu là cha của v,v,v, rồi định hướng cạnh đó theo chiều (u→v),(u rightarrow v),(u→v), thì ta sẽ thu được một đồ thị mới dạng cây, gọi là cây DFStext{DFS}DFS. Các cạnh được giữ lại sẽ gọi là cạnh thuộc cây DFS,text{DFS},DFS, còn các cạnh không được giữ lại gọi là cạnh không thuộc cây DFStext{DFS}DFS.
Cây DFS của một đồ thị gồm 9 đỉnh, các cạnh màu trắng là cạnh được giữ lại
Giả sử đồ thị đang xét là đồ thị có hướng, xét mọi cung được thăm và không được thăm trong quá trình DFS,text{DFS},DFS, ta có các loại cung sau:
- Cung của cây DFS (Tree Edges): Các cung được thăm trong quá trình DFStext{DFS}DFS (cung màu trắng nét liền).
- Cung xuôi (Forward edges): Cung không thuộc cây DFStext{DFS}DFS có dạng (u→v)(u rightarrow v)(u→v); trong đó uuu là cha của vvv trong quá trình DFStext{DFS}DFS (cạnh xanh lá).
- Cung ngược (Back edges): Cung không thuộc cây DFStext{DFS}DFS và có dạng (v→u)(v rightarrow u)(v→u); trong đó uuu là cha của vvv (cạnh đỏ) nhưng vvv đã được thăm trước đó do một dây chuyền DFStext{DFS}DFS khác.
- Cung chéo (Cross edges): Cung không thuộc cây DFStext{DFS}DFS, trong đó uuu và vvv thuộc hai nhánh khác nhau của cùng một cây DFStext{DFS}DFS (cạnh tím).
Còn nếu như xét trên đồ thị vô hướng, thì chỉ tồn tại duy nhất hai loại cung là cung thuộc cây DFS và cung ngược (không thuộc cây DFS).
Phân tích giải thuật
Từ định nghĩa về cây DFStext{DFS}DFS ở trên, ta nhận thấy rằng:
- Một cây DFStext{DFS}DFS của đồ thị sẽ chứa toàn bộ các đỉnh thuộc cùng một thành phần liên thông của đồ thị, nhưng không phải tất cả các cạnh.
- Cây DFStext{DFS}DFS của đồ thị là một đồ thị không có chu trình.
- Nếu như trong quá trình duyệt DFS,text{DFS},DFS, xuất hiện một cung ngược, thì chắc chắn thành phần liên thông hiện tại có chứa chu trình (bời vì sẽ có một đường đi quay lại được đỉnh đã thăm ở phía trên).
Nhận xét trên cho ta ý tưởng về cách xác định một đồ thị có chu trình hay không vô cùng đơn giản như sau:
Sử dụng DFS, duyệt từng thành phần liên thông của đồ thị. Nếu trong quá trình duyệt phát hiện một cung ngược, thì chắc chắn đồ thị có chứa chu trình.
Việc xác định một cung có phải cung ngược hay không rất dễ, bằng cách sử dụng một mảng visited[u]text{visited}[u]visited[u] để đánh dấu lại đỉnh uuu đã duyệt qua hay chưa. Sau đó, nếu như trong quá trình duyệt nhánh textDFStext{DFS}textDFS gốc uuu mà có một cạnh (u,v)(u, v)(u,v) mà vvv đã thăm rồi, thì cung (u→v)(u rightarrow v)(u→v) sẽ là cung ngược.
Giải thuật có thể thực hiện tương tự nhau ở cả đồ thị vô hướng lẫn có hướng.
3. Cài đặt
Ngôn ngữ C++:
#include <bits/stdc++.h> #define int long long #define task “detect_cycle.” using namespace std; const int maxn = 1e5 + 10; typedef int arr[maxn]; vector < int > adj[maxn]; // Nhập dữ liệu đồ thị. void enter(int &n, int &m, vector < int > adj[]) { cin >> n >> m; for (int u = 1; u <= n; ++u) adj[u].clear(); for (int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } } // DFS để tìm chu trình từ một cây DFS gốc u. bool dfs_find_cycle(int u, int par, vector < int > adj[], arr visited) { visited[u] = true; for (int v: adj[u]) { // Nếu đỉnh v chưa thăm thì đi thăm v và xem nhánh DFS từ v // có tạo ra chu trình hay không. if (!visited[v]) { if (dfs_find_cycle(v, u, adj, visited)) return true; } // Nếu v đã thăm và v không phải đỉnh vừa gọi đệ quy ở bước // trước, thì cung (u, v) là một cung ngược -> có chu trình. else if (v != par) return true; } return false; } // Xác định có tồn tại chu trình trên đồ thị hay không. void solution(int n, vector < int > adj[], arr visited) { fill(visited + 1, visited + n + 1, 0); // Thử DFS từ các đỉnh và dựng cây DFS. for (int u = 1; u <= n; ++u) if (!visited[u]) { if (dfs_find_cycle(u, -1, adj, visited)) { cout << “YES” << endl; return; } } cout << “NO” << endl; } main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; arr visited; enter(n, m, adj); solution(n, adj, visited); return 0; }
1. Bài toán 1
Đề bài
Cho một dãy số AAA gồm nnn phần tử a0,a1,…,an−1a_0, a_1, dots, a_{n – 1}a0,a1,…,an−1. Xuất phát từ một phần tử ở vị trí iii bất kỳ, ta sẽ di chuyển trên mảng theo trình tự sau:
- Nếu ai<0,a_i < 0,ai<0, di chuyển tới phần tử (i−ai) mod n(i – a_i) text{ mod } n(i−ai) mod n.
- Nếu ai>0,a_i > 0,ai>0, di chuyển tới phần tử (i+ai) mod n(i + a_i) text{ mod } n(i+ai) mod n.
Nếu như giá trị ai mod n=0,a_i text{ mod } n = 0,ai mod n=0, thì sẽ không có sự di chuyển nào diễn ra cả.
Hãy xác định xem quá trình di chuyển trên có thể tạo thành một chu trình di chuyển trên dãy số hay không? Lưu ý rằng, nếu như bước di chuyển tự đi tới chính nó thì không tính là một chu trình.
Input:
- Dòng đầu tiên chứa số nguyên dương n (1≤n≤105)n (1 le n le 10^5)n (1≤n≤105).
- Dòng thứ hai chứa nnn số nguyên a0,a1,…,an−1a_0, a_1, dots, a_{n – 1}a0,a1,…,an−1 phân tách nhau bởi dấu cách (∣ai∣≤106;ai≠0,∀i:0≤i<n)big(|a_i| le 10^6; a_i ne 0, forall i: 0 le i < nbig)(∣ai∣≤106;ai=0,∀i:0≤i<n).
Output:
- In ra YES nếu như có thể tạo ra một chu trình di chuyển trên dãy số, ngược lại in ra NO.
Sample Input 1:
5 2 -1 1 2 2
Sample Output 1:
YES
Sample Input 2:
2 1 2
Sample Output 2:
NO
Ý tưởng
Nếu như ta đồ thị hóa bài toán, coi các vị trí iii trên dãy số là các đỉnh của một đồ thị, và giữa hai vị trí i,ji, ji,j có cạnh nối nếu như từ vị trí iii có thể di chuyển được tới vị trí jjj theo cách di chuyển trong đề bài, thì bài toán sẽ trở thành xác định xem trên đồ thị có tồn tại chu trình hay không.
Trước tiên sử dụng một mảng adj[u]text{adj}[u]adj[u] để lưu các vị trí mà từ vị trí uuu có thể di chuyển tới được, coi như đây là một danh sách kề của đồ thị. Sau đó tiến hành DFStext{DFS}DFS tìm đường như giải thuật bên trên.
Cài đặt
Ngôn ngữ C++:
#include <bits/stdc++.h> #define int long long #define task “loop_in_seq.” #define inf 1e9 + 7 #define x first #define y second using namespace std; const int maxn = 1e5 + 10; typedef int arr[maxn]; vector < int > adj[maxn]; // Nhập dữ liệu dãy số. void enter(int &n, arr a) { cin >> n; for (int i = 0; i < n; ++i) cin >> a[i]; } // Dựng đồ thị. void create_graph(int n, arr a, vector < int > adj[]) { for (int i = 0; i < n; ++i) if (i != (i + a[i] + n) % n) adj[i].push_back((i + a[i] + n) % n); } // DFS để tìm chu trình từ một cây DFS gốc u. bool dfs_find_cycle(int u, int par, vector < int > adj[], arr visited) { visited[u] = true; for (int v: adj[u]) { // Nếu đỉnh v chưa thăm thì đi thăm v và xem nhánh DFS từ v // có tạo ra chu trình hay không. if (!visited[v]) { if (dfs_find_cycle(v, u, adj, visited)) return true; } // Nếu v đã thăm và v không phải đỉnh vừa gọi đệ quy ở bước // trước, thì cung (u, v) là một cung ngược -> có chu trình. else if (v != par) return true; } return false; } // Tìm chu trình trong dãy số. void solution(int n, arr a, vector < int > adj[]) { create_graph(n, a, adj); arr visited; fill(visited, visited + n, 0); for (int i = 0; i < n; ++i) if (!visited[i]) if (dfs_find_cycle(i, -1, adj, visited)) { cout << “YES”; return; } cout << “NO”; } main() { //freopen(task”inp”, “r”, stdin); //freopen(task”out”, “w”, stdout); ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; arr a; enter(n, a); solution(n, a, adj); return 0; }
Đánh giá độ phức tạp
Độ phức tạp chỉ là O(n+m)O(n + m)O(n+m) cho quá trình DFS,text{DFS},DFS, với mmm là số cạnh nối tạo ra trên đồ thị.
2. Bài toán 2
Đề bài
Cho một đơn đồ thị vô hướng liên thông gồm nnn đỉnh, các đỉnh được đánh số từ 000 và mmm cạnh. Hãy đếm số lượng chu trình đơn có kkk đỉnh và kkk cạnh trong đồ thị đó?
Input:
- Dòng đầu tiên chứa ba số nguyên dương n,mn, mn,m và k (2≤n,m≤100;1≤k≤m)k (2 le n, m le 100; 1 le k le m)k (2≤n,m≤100;1≤k≤m).
- mmm dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u,vu, vu,v – thể hiện đồ thị có một cạnh nối hai chiều giữa hai đỉnh uuu và vvv.
Output:
- Số nguyên duy nhất là số lượng chu trình tìm được. Lưu ý, các chu trình có cùng các đỉnh và các cạnh nhưng khác thứ tự sẽ vẫn chỉ tính là 111 chu trình.
Sample Input:
5 6 4 0 1 0 3 1 4 1 2 2 3 4 3
Sample Output:
3
Giải thích:
Các chu trình tìm được là: (0,1,2,3,0);(0,1,4,3,0);(1,2,3,4,1)(0, 1, 2, 3, 0); (0, 1, 4, 3, 0); (1, 2, 3, 4, 1)(0,1,2,3,0);(0,1,4,3,0);(1,2,3,4,1). Lưu ý rằng, hai chu trình (0,3,2,1,0)(0, 3, 2, 1, 0)(0,3,2,1,0) và (0,1,2,3,0)(0, 1, 2, 3, 0)(0,1,2,3,0) chỉ được tính 111 lần, do đó đáp án chỉ là 333.
Ý tưởng
Thay vì tìm một chu trình có độ dài n,n,n, ta có thể tìm ra các đường đi có độ dài n−1n – 1n−1 từ mọi đỉnh u,u,u, sau đó kiểm tra xem đỉnh cuối cùng của đường đi tìm được có đến được đỉnh uuu ban đầu hay không. Nếu có thì đó là một chu trình có độ dài nnn.
Tuy nhiên, để giảm số lần phải duyệt chu trình, thì ta nhận xét rằng: Chỉ cần lựa chọn đỉnh xuất phát là một trong số n−(k−1)n – (k – 1)n−(k−1) đỉnh đầu tiên. Lí do là bởi vì, nếu như thực sự tồn tại chu trình độ dài kkk khi duyệt DFStext{DFS}DFS thì nhiệm vụ của chúng ta là phải tìm ra một đường đi độ dài k−1k – 1k−1 trong số k−1k – 1k−1 đỉnh còn lại. Việc chọn đỉnh xuất phát ngoài tập n−(k−1)n – (k – 1)n−(k−1) đỉnh đầu tiên sẽ chỉ khiến cho số lượng chu trình trùng lặp bị tăng lên.
Một điều cần lưu ý là, mỗi khi chọn một đỉnh xuất phát để tìm chu trình từ nó, thì số lượng chu trình tìm được sẽ bị lặp lại 222 lần (do chu trình có thể đi theo hai chiều xuôi chiều kim đồng hồ hoặc ngược chiều kim đồng hồ). Vì thế, kết quả cuối cùng cần chia cho 222.
Cài đặt
Ngôn ngữ C++:
#include <bits/stdc++.h> #define task “count_cycle.” using namespace std; const int maxn = 101; typedef int arr[maxn]; vector < int > adj[maxn]; void enter(int &n, int &m, int &k, vector < int > adj[]) { cin >> n >> m >> k; for (int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } } void dfs(int start, int k, int u, vector < int > adj[], arr visited, int &total_cycle) { visited[u] = 1; // Đã tìm ra đường đi độ dài k – 1. if (k == 0) { // Loại bỏ đỉnh u khỏi chu trình để chọn đường đi khác. visited[u] = 0; // Kiểm tra xem đỉnh u có quay về được đỉnh xuất phát ban đầu không. // Nghĩa là đỉnh ban đầu nằm trong danh sách kề của đỉnh u. if (find(adj[u].begin(), adj[u].end(), start) != adj[u].end()) ++total_cycle; return; } // Tìm các đường đi có thể bằng DFS. Mục tiêu là tạo được đường đi // có độ dài bằng k – 1. for (int v: adj[u]) { if (visited[v]) continue; dfs(start, k – 1, v, adj, visited, total_cycle); } // Loại bỏ đỉnh u khỏi chu trình để chọn một đường đi khác. visited[u] = 0; } void solution(int n, int k, vector < int > adj[]) { arr visited; fill(visited, visited + n, 0); int total_cycle = 0; for (int u = 0; u < n – (k – 1); ++u) if (!visited[u]) { // Nếu u chưa thăm thì dựng tất cả các chu trình độ dài // n xuất phát từ u. dfs(u, k – 1, u, adj, visited, total_cycle); // Đánh dấu lại u đã sử dụng rồi, từ sau đây sẽ không tìm // thêm các chu trình chứa u nữa -> tránh lặp lại. visited[u] = 1; } // Chia 2 kết quả vì số chu trình đã đếm bị lặp lại hai lần. cout << total_cycle / 2; } main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m, k; enter(n, m, k, adj); solution(n, k, adj); return 0; }
Đánh giá độ phức tạp
Ta thử chọn n−(k−1)n – (k – 1)n−(k−1) đỉnh làm điểm bắt đầu của chu trình, và lại mất thêm O(n+m)O(n + m)O(n+m) để thực hiện DFStext{DFS}DFS tìm chu trình, do đó độ phức tạp tổng quát sẽ là O(n×(n+m))Obig(n times (n + m)big)O(n×(n+m)).
- Sách Giải thuật và Lập trình – thầy Lê Minh Hoàng.
- Tài liệu giáo khoa chuyên Tin quyển 1 – thầy Hồ Sĩ Đàm.
- https://www.geeksforgeeks.org/cycles-of-length-n-in-an-undirected-and-connected-graph/
- https://www.geeksforgeeks.org/detect-cycle-undirected-graph/
- https://www.geeksforgeeks.org/check-loop-array-according-given-constraints/
©️ Tác giả: Vũ Quế Lâm từ Viblo