Giả sử có N cặp đôi và họ ngồi trên 2N ghế xếp thành một hàng và muốn nắm tay nhau. Chúng ta phải tìm số lần hoán vị tối thiểu sao cho mọi cặp đôi đều ngồi cạnh nhau.
Mọi người và ghế được biểu diễn bằng số từ 0 đến 2N-1, các cặp được đánh số theo thứ tự, ví dụ cặp đầu tiên là (0, 1), cặp thứ hai là (2, 3), và cứ thế cho đến cặp cuối cùng là (2N-2, 2N-1).
Sắp xếp ban đầu của các cặp được cho bởi một mảng khác gọi là row, và row[i] là giá trị của người ngồi ban đầu ở ghế thứ i.
Vì vậy, nếu đầu vào giống như [0,2,4,1,3,5], thì đầu ra sẽ là 2.
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau −
Định nghĩa một khối dữ liệu gọi là UF, trong khối này định nghĩa một số thuộc tính và hàm như sau −
Định nghĩa mảng parent
Khởi tạo khối UF bằng cách nhận giá trị N, sau đó thực hiện như sau −
count := N
parent := mảng kích thước N
for khởi tạo i := 0, khi i < N, cập nhật (tăng i lên 1), thực hiện −
parent[i] := i
parent[i] := i
parA := getParent(a)
parB := getParent(b)
nếu parA bằng parB, thì −
trả về
(giảm count xuống 1)
parent[parB] := parA
Định nghĩa hàm getParent(), nhận i,
nếu parent[i] bằng i, thì −
trả về i
trả về parent[i] = getParent(parent[i])
Từ phương thức main thực hiện như sau −
n := kích thước của row, N := n / 2
tạo một khối UF gọi là uf và khởi tạo với N
for khởi tạo gr := 0, khi gr < N, cập nhật (tăng gr lên 1), thực hiện −
a := row[gr * 2]
b := row[gr * 2 + 1]
gọi unionn(a / 2, b / 2) của uf
trả về N - count của uf
Hãy xem triển khai sau để hiểu rõ hơn −
Ví dụ
#include <bits/stdc++.h> using namespace std; class Solution { public: class UF{ public: vector<int> parent; int count; UF(int N){ count = N; parent = vector<int>(N); for (int i = 0; i < N; i++) { parent[i] = i; } } void unionn(int a, int b){ int parA = getParent(a); int parB = getParent(b); if (parA == parB) return; count--; parent[parB] = parA; } int getParent(int i){ if (parent[i] == i) return i; return parent[i] = getParent(parent[i]); } }; int minSwapsCouples(vector<int>& row) { int n = row.size(); int N = n / 2; UF uf(N); for (int gr = 0; gr < N; gr++) { int a = row[gr * 2]; int b = row[gr * 2 + 1]; uf.unionn(a / 2, b / 2); } return N - uf.count; } }; main(){ Solution ob; vector<int> v = {0,2,4,1,3,5}; cout << (ob.minSwapsCouples(v)); } Đầu vào
{0,2,4,1,3,5} Đầu ra
2