You are viewing a single comment's thread. Return to all comments →
O(n)
int minimumSwaps(int n, const vector<int>& arr) { vector<vector<int>> cycles; vector<bool> visited(n+1); for (int i = 1; i <= n; ++i) { if (visited[arr[i]]) continue; cycles.push_back({arr[i]}); int travel = arr[i]; visited[travel] = true; while (arr[travel] != cycles.back()[0]) { cycles.back().push_back(arr[travel]); travel = arr[travel]; visited[travel] = true; } } int moves = 0; for (vector<int> cycle : cycles) moves = moves + cycle.size() - 1; return moves; } int main() { int n, k; vector<int> arr = {-1}; cin >> n; for (int i=1; i <= n; ++i) { cin >> k; arr.push_back(k); } cout << minimumSwaps(n, arr); }
Seems like cookies are disabled on this browser, please enable them to open this website
Minimum Swaps 2
You are viewing a single comment's thread. Return to all comments →
O(n)