HackerEarth Permutation problem solution

In this HackerEarth Permutation problem solution A permutation is a list of K numbers, each between 1 and K (both inclusive), that has no duplicate elements.

Permutation X is lexicographically smaller than Permutation Y if for some i <= K:

All of the first i-1 elements of X are equal to first i-1 elements of Y.

ith element of X is smaller than ith element of Y.

You are given a permutation P, you can exchange some of its elements as many times as you want in any order. You have to find the lexicographically smallest Permutation that you can obtain from P.

K is less than 101.

HackerEarth Permutation problem solution.

#include <bits/stdc++.h>

using namespace std;

int arr [100 + 10];
char board [100 + 10][100 + 10];
bool chosen [100 + 10];
bool vis[100 + 10];
vector < int > v[100 + 10];
int pos [100 + 10];

int ans = -1;

void dfs(int index){

    vis[ index ] = true;
    if(!chosen[index]) ans = min(ans , arr[index]); //check if the number isn't chosen before

    for(int i = 0; i < (int) v[index].size(); i++){

        if(vis[ v[index][i] ] ) continue;   // check if the number was visited before
        int e = v[index][i];          // check the available transitions
        dfs( e );
    }
}

int main()
{

    int n;

    cin >> n;

    for(int i = 0; i < n; i++){

        cin >> arr[i];
        pos[ arr[i] ] = i;          // store the original index of eah number
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){

            cin >> board[i][j];
            if(board[i][j] == 'Y')
                v[i].push_back(j);
        }
    }

    for(int i = 0; i < n; i++){

        memset(vis, false, sizeof vis);     // set all numbers as unvisited
        ans = 1e9;
        dfs(i);
        chosen[ pos[ans] ] = true;           // put this index as already chosen
        cout << ans << " ";
    }

    return 0;
}

coding problems solutions