Giả sử ta có danh sách số row biểu diễn vớ nằm ngang hàng. Chúng chưa sắp xếp, nhưng ta muốn sắp xếp sao cho mỗi cặp vớ cạnh nhau như (0,1), (2,3), (4,5), v.v. Ta phải tìm số lần hoán vị tối thiểu để sắp xếp lại.
Ví dụ: row = [0, 5, 6, 2, 1, 3, 7, 4], đầu ra = 2, các bước:
- [0, 5, 6, 2, 1, 3, 7, 4]
- [0, 1, 6, 2, 5, 3, 7, 4]
- [0, 1, 3, 2, 5, 6, 7, 4]
- [0, 1, 3, 2, 5, 4, 7, 6]
Để giải quyết, ta dùng Union-Find (DSU):
- Định nghĩa mảng p và sz.
- Hàm find(u): trả về u nếu p[u]==u, ngược lại p[u]=find(p[u]).
- Hàm join(u,v): gộp hai tập hợp.
- Từ main: n = arr.size()/2; khởi tạo p[i]=i, sz[i]=1.
- for i=0; i
- ans=0; for i=0; i
- Trả về ans.
- ans=0; for i=0; i
Xem triển khai dưới đây:
Ví dụ
#include <bits/stdc++.h> using namespace std; vector<int> p, sz; int find(int u) { return p[u] == u ? u : p[u] = find(p[u]); } void join(int u, int v) { int pu = find(u), pv = find(v); if (pu == pv) return; if (sz[pu] >= sz[pv]) { p[pv] = pu; sz[pu] += sz[pv]; }else { p[pu] = pv; sz[pv] += sz[pu]; } } int solve(vector<int>& arr) { int n = arr.size() / 2; p = vector<int>(n); for (int i = 0; i < n; ++i) p[i] = i; sz = vector<int>(n, 1); for (int i = 0; i < n; ++i) { int u = arr[i << 1] / 2; int v = arr[i << 1 | 1] / 2; join(u, v); } int ans = 0; for (int i = 0; i < n; ++i) if (find(i) == i) ans += sz[i] - 1; return ans; } int main(){ vector<int> v = {0, 5, 6, 2, 1, 3, 7, 4}; cout << solve(v); }
Đầu vào
{2, 4, 6, 3}
Đầu ra
23