Vấn đề về Chu trình trên đồ thị

Từ những bài viết đầu tiên về chuyên đề Lý thuyết đồ thị, tôi đã giới thiệu tới các bạn khái niệm về Chu trình trên đồ thị. Một đường đi {v0,v1,v2,…,vk}{v_0, v_1, v_2, dots, v_k}{v0,v1,v2,…,vk} trên đồ thị được gọi là một chu trình nếu như v0=vk,v_0 = v_k,v0=vk, và nếu như các cạnh trên đường đi đó đều phân biệt. Ngoài ra, trên đồ thị còn có thể tồn tại hai dạng chu trình đặc biệt là Chu trình Euler và Chu trình Hamilton, sẽ được đề cập tới ở những bài viết tiếp theo.

Trong bài viết này, chúng ta sẽ cùng nhau đi sâu hơn vào cách xác định chu trình trên đồ thị và những bài toán ứng dụng của nó.

Giải thuật DFStext{DFS}DFS là một công cụ rất hữu hiệu để xác định chu trình trên đồ thị. Sau đây, chúng ta sẽ cùng tìm hiểu về ý tưởng của giải thuật.

1. Phát biểu bài toán

Cho một đơn đồ thị vô hướng GGG gồm nnn đỉnh và mmm cung (có thể có "khuyên" - cạnh tự nối một đỉnh với chính nó). Các đỉnh của đồ thị được đánh số từ 111 tới nnn.

Một chu trình trên đồ thị là một đường đi (x1,x2,…,xk,x1)(x_1, x_2, dots, x_k, x_1)(x1,x2,…,xk,x1) với hai đỉnh đầu và cuối của đường đi giống nhau.

Hãy xác định đồ thị trên có chứa chu trình nào hay không?

Input:

Dòng đầu tiên chứa hai số nguyên nnn và mmm - số đỉnh và số cạnh của đồ thị (1≤n,m≤105)(1 le n, m le 10^5)(1≤n,m≤105).
mmm dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u,vu, vu,v - thể hiện một cạnh của đồ thị nối hai đỉnh uuu và vvv.

Output:

In ra YES nếu đồ thị có chứa chu trình, ngược lạ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:

2. Ý tưởng

Phân loại các cung trên cây DFS

Trong quá trình duyệt DFStext{DFS}DFS trên đồ thị, nếu như ta chỉ giữ lại các cạnh (u,v)(u, v)(u,v) với uuu là cha của v,v,v, rồi định hướng cạnh đó theo chiều (u→v),(u rightarrow v),(u→v), thì ta sẽ thu được một đồ thị mới dạng cây, gọi là cây DFStext{DFS}DFS. Các cạnh được giữ lại sẽ gọi là cạnh thuộc cây DFS,text{DFS},DFS, còn các cạnh không được giữ lại gọi là cạnh không thuộc cây DFStext{DFS}DFS.

Vấn đề về Chu trình trên đồ thị

Cây DFS của một đồ thị gồm 9 đỉnh, các cạnh màu trắng là cạnh được giữ lại

Giả sử đồ thị đang xét là đồ thị có 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).

Vấn đề về Chu trình trên đồ thị

Còn nếu như xét trên đồ thị vô hướng, thì chỉ tồn tại duy nhất hai loại cung là cung thuộc cây DFS và cung ngược (không thuộc cây DFS).

Phân tích giải thuật

Từ định nghĩa về cây DFStext{DFS}DFS ở trên, ta nhận thấy rằng:

Một cây DFStext{DFS}DFS của đồ thị sẽ chứa toàn bộ các đỉnh thuộc cùng một thành phần liên thông của đồ thị, nhưng không phải tất cả các cạnh.
Cây DFStext{DFS}DFS của đồ thị là một đồ thị không có chu trình.
Nếu như trong quá trình duyệt DFS,text{DFS},DFS, xuất hiện một cung ngược, thì chắc chắn thành phần liên thông hiện tại có chứa chu trình (bời vì sẽ có một đường đi quay lại được đỉnh đã thăm ở phía trên).

Nhận xét trên cho ta ý tưởng về cách xác định một đồ thị có chu trình hay không vô cùng đơn giản như sau:

Sử dụng DFS, duyệt từng thành phần liên thông của đồ thị. Nếu trong quá trình duyệt phát hiện một cung ngược, thì chắc chắn đồ thị có chứa chu trình.

Việc xác định một cung có phải cung ngược hay không rất dễ, bằng cách sử dụng một mảng visited[u]text{visited}[u]visited[u] để đánh dấu lại đỉnh uuu đã duyệt qua hay chưa. Sau đó, nếu như trong quá trình duyệt nhánh textDFStext{DFS}textDFS gốc uuu mà có một cạnh (u,v)(u, v)(u,v) mà vvv đã thăm rồi, thì cung (u→v)(u rightarrow v)(u→v) sẽ là cung ngược.

Giải thuật có thể thực hiện tương tự nhau ở cả đồ thị vô hướng lẫn có hướng.

3. Cà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 đồ thị. 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 để tìm chu trì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 đỉnh v chưa thăm thì đi thăm v và xem nhánh DFS từ v // có tạo ra chu trình hay không. if (!visited[v]) { if (dfs_find_cycle(v, u, adj, visited)) return true; } // Nếu v đã thăm và v không phải đỉnh vừa gọi đệ quy ở bước // trước, thì cung (u, v) là một cung ngược -> có chu trình. else if (v != par) return true; } return false; } // Xác định có tồn tại chu trình trên đồ thị hay không. void solution(int n, vector < int > adj[], arr visited) { fill(visited + 1, visited + n + 1, 0); // Thử DFS từ các đỉnh và 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. Bài toán 1

Đề bài

Cho một dã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 phát từ một phần tử ở vị trí iii bất kỳ, ta sẽ di chuyển trên mảng theo trì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ư giá trị ai mod n=0,a_i text{ mod } n = 0,ai mod n=0, thì sẽ không có sự di chuyển nào diễn ra cả.

Hãy xác định xem quá trình di chuyển trên có thể tạo thành một chu trình di chuyển trên dãy số hay không? Lưu ý rằng, nếu như bước di chuyển tự đi tới chính nó thì không tính là một chu trình.

Input:

Dò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).
Dò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 tách nhau bởi dấu cá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ư có thể tạo ra một chu trình di chuyển trên dãy số, ngược lạ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:

Ý tưởng

Nếu như ta đồ thị hóa bài toán, coi các vị trí iii trên dãy số là các đỉnh của một đồ thị, và giữa hai vị trí i,ji, ji,j có cạnh nối nếu như từ vị trí iii có thể di chuyển được tới vị trí jjj theo cách di chuyển trong đề bài, thì bài toán sẽ trở thành xác định xem trên đồ thị có tồn tại chu trình hay không.

Trước tiên sử dụng một mảng adj[u]text{adj}[u]adj[u] để lưu các vị trí mà từ vị trí uuu có thể di chuyển tới được, coi như đây là một danh sách kề của đồ thị. Sau đó tiến hành DFStext{DFS}DFS tìm đường như giải thuật bên trên.

Cà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 dãy số. void enter(int &n, arr a) { cin >> n; for (int i = 0; i < n; ++i) cin >> a[i]; } // Dựng đồ thị. 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 để tìm chu trì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 đỉnh v chưa thăm thì đi thăm v và xem nhánh DFS từ v // có tạo ra chu trình hay không. if (!visited[v]) { if (dfs_find_cycle(v, u, adj, visited)) return true; } // Nếu v đã thăm và v không phải đỉnh vừa gọi đệ quy ở bước // trước, thì cung (u, v) là một cung ngược -> có chu trình. else if (v != par) return true; } return false; } // Tìm chu trình trong dã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; }

Đánh giá độ phức tạp

Độ phức tạp chỉ là O(n+m)O(n + m)O(n+m) cho quá trình DFS,text{DFS},DFS, với mmm là số cạnh nối tạo ra trên đồ thị.

2. Bài toán 2

Đề bài

Cho một đơn đồ thị vô hướng liên thông gồm nnn đỉnh, các đỉnh được đánh số từ 000 và mmm cạnh. Hãy đếm số lượng chu trình đơn có kkk đỉnh và kkk cạnh trong đồ thị đó?

Input:

Dòng đầu tiên chứa ba số nguyên dương n,mn, mn,m và 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 dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u,vu, vu,v - thể hiện đồ thị có một cạnh nối hai chiều giữa hai đỉnh uuu và vvv.

Output:

Số nguyên duy nhất là số lượng chu trình tìm được. Lưu ý, các chu trình có cùng các đỉnh và các cạnh nhưng khác thứ tự sẽ vẫn chỉ tính là 111 chu trình.

Sample Input:

5 6 4 0 1 0 3 1 4 1 2 2 3 4 3

Sample Output:

Giải thích:

Các chu trình tìm được là: (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 ý rằng, hai chu trình (0,3,2,1,0)(0, 3, 2, 1, 0)(0,3,2,1,0) và (0,1,2,3,0)(0, 1, 2, 3, 0)(0,1,2,3,0) chỉ được tính 111 lần, do đó đáp án chỉ là 333.

Ý tưởng

Thay vì tìm một chu trình có độ dài n,n,n, ta có thể tìm ra các đường đi có độ dài n−1n - 1n−1 từ mọi đỉnh u,u,u, sau đó kiểm tra xem đỉnh cuối cùng của đường đi tìm được có đến được đỉnh uuu ban đầu hay không. Nếu có thì đó là một chu trình có độ dài nnn.

Tuy nhiên, để giảm số lần phải duyệt chu trình, thì ta nhận xét rằng: Chỉ cần lựa chọn đỉnh xuất phát là một trong số n−(k−1)n - (k - 1)n−(k−1) đỉnh đầu tiên. Lí do là bởi vì, nếu như thực sự tồn tại chu trình độ dài kkk khi duyệt DFStext{DFS}DFS thì nhiệm vụ của chúng ta là phải tìm ra một đường đi độ dài k−1k - 1k−1 trong số k−1k - 1k−1 đỉnh còn lại. Việc chọn đỉnh xuất phát ngoài tập n−(k−1)n - (k - 1)n−(k−1) đỉnh đầu tiên sẽ chỉ khiến cho số lượng chu trình trùng lặp bị tăng lên.

Một điều cần lưu ý là, mỗi khi chọn một đỉnh xuất phát để tìm chu trình từ nó, thì số lượng chu trình tìm được sẽ bị lặp lại 222 lần (do chu trình có thể đi theo hai chiều xuôi chiều kim đồng hồ hoặc ngược chiều kim đồng hồ). Vì thế, kết quả cuối cùng cần chia cho 222.

Cà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; // Đã tìm ra đường đi độ dài k - 1. if (k == 0) { // Loại bỏ đỉnh u khỏi chu trình để chọn đường đi khác. visited[u] = 0; // Kiểm tra xem đỉnh u có quay về được đỉnh xuất phát ban đầu không. // Nghĩa là đỉnh ban đầu nằm trong danh sách kề của đỉnh u. if (find(adj[u].begin(), adj[u].end(), start) != adj[u].end()) ++total_cycle; return; } // Tìm các đường đi có thể bằng DFS. Mục tiêu là tạo được đường đi // có độ dài bằng k - 1. for (int v: adj[u]) { if (visited[v]) continue; dfs(start, k - 1, v, adj, visited, total_cycle); } // Loại bỏ đỉnh u khỏi chu trình để chọn một đường đi khá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 thì dựng tất cả các chu trình độ dài // n xuất phát từ u. dfs(u, k - 1, u, adj, visited, total_cycle); // Đánh dấu lại u đã sử dụng rồi, từ sau đây sẽ không tìm // thêm các chu trình chứa u nữa -> tránh lặp lại. visited[u] = 1; } // Chia 2 kết quả vì số chu trình đã đếm bị lặp lạ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; }

Đánh giá độ phức tạp

Ta thử chọn n−(k−1)n - (k - 1)n−(k−1) đỉnh làm điểm bắt đầu của chu trình, và lại mất thêm O(n+m)O(n + m)O(n+m) để thực hiện DFStext{DFS}DFS tìm chu trình, do đó độ phức tạp tổng quát sẽ là 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/