# Minimum Swaps 2 C++ Solution

#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

vector<int>v[100003];
bool visit[100003];

// This function return the size of the cycle as mentioned in the explanation.
int dfs(int i)
{
visit[i] = true;
int z = 1;

for(auto x: v[i])
if(!visit[x])
z += dfs(x);

return z;
}

int minimumSwaps(vector<int> A) {

for(int i = 0; i < A.size(); ++i )
v[i].push_back(A[i]-1), v[A[i]-1].push_back(i);

int c = 0;

for(int i = 0; i < A.size(); ++i)
{
if(!visit[i])
c += dfs(i) - 1;
}

return c;
}
int main()
{
ofstream fout(getenv("OUTPUT_PATH"));

int n;
cin >> n;
cin.ignore(numeric_limits<streamsize>::max(), '\n');

string arr_temp_temp;
getline(cin, arr_temp_temp);

vector<string> arr_temp = split_string(arr_temp_temp);

vector<int> arr(n);

for (int i = 0; i < n; i++) {
int arr_item = stoi(arr_temp[i]);

arr[i] = arr_item;
}

int res = minimumSwaps(arr);

fout << res << "\n";

fout.close();

return 0;
}

vector<string> split_string(string input_string) {
string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
return x == y and x == ' ';
});

input_string.erase(new_end, input_string.end());

while (input_string[input_string.length() - 1] == ' ') {
input_string.pop_back();
}

vector<string> splits;
char delimiter = ' ';

size_t i = 0;
size_t pos = input_string.find(delimiter);

while (pos != string::npos) {
splits.push_back(input_string.substr(i, pos - i));

i = pos + 1;
pos = input_string.find(delimiter, i);
}

splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

return splits;
}

### Subscribe to The Poor Coder | Algorithm Solutions

Don’t miss out on the latest issues. Sign up now to get access to the library of members-only issues.
[email protected]
Subscribe