C++ program to find out the maximum value of i

Suppose, we have a permutation of integers 'seq' and an array of integer pairs 'pairs' of size m that contains integers 0 to n - 1. Now, we perform the following operation on seq as many times as possible so that seq[i] = i (0 ≤ i < n) is maximized.

• We have to choose an integer j where 0 <= j < m, and then swap seq[first value of pair[j]] and seq[second value of pair[j]]

We have to find out the maximum value of i so that seq[i] = i after performing the operation multiple times.

So, if the input is like n = 4, m = 2, seq = {0, 3, 2, 1}, pairs = {{0, 1}, {2, 3}}, then the output will be 2.

The maximum possible value is 2.

To solve this, we will follow these steps −

N := 100 Define an array tp of size: N. Define arrays vtmp, vis of size N. Define a function dfs(), this will take j, k, tp[j] := k insert j at the end of vtmp[k] for each value b in vis[j], do:    if tp[b] is not equal to 0, then:       Ignore following part, skip to the next iteration    dfs(b, k) res := 0 for initialize i := 0, when i < n, update (increase i by 1), do:    if seq[i] is same as i, then:       (increase res by 1) for initialize i := 0, when i < m, update (increase i by 1), do:    a := first value of pairs[i]    b := second value of pairs[i]    insert b at the end of vis[a]   insert a at the end of vis[b] idx := 1 for initialize i := 0, when i < n, update (increase i by 1), do: if tp[i] is same as 0, then: dfs(i, idx) for each element j in vtmp[idx], do: if tp[seq[j]] is same as idx and seq[j] is not equal to j, then: (increase res by 1) (increase idx by 1) print(res)

Example

Let us see the following implementation to get better understanding −

#include <bits/stdc++.h> using namespace std; const int INF = 1e9; #define N 100 int tp[N]; vector<int> vtmp[N], vis[N]; void dfs(int j, int k){    tp[j] = k;    vtmp[k].push_back(j);    for(auto b : vis[j]) {       if(tp[b] != 0)          continue;       dfs(b, k);    } } void solve(int n, int m, int seq[], vector<pair<int, int>> pairs) {    int res = 0;    for(int i = 0; i < n; i++){       if(seq[i] == i)          res++;    }    for(int i = 0; i < m; i++){       int a = pairs[i].first;       int b = pairs[i].second;       vis[a].push_back(b);       vis[b].push_back(a);    }    int idx = 1;    for(int i = 0; i < n; i++) {       if(tp[i] == 0) {          dfs(i, idx);          for(auto j: vtmp[idx]){             if(tp[seq[j]] == idx && seq[j] != j)                res++;          }          idx++;       }    } cout<< res; } int main() { int n = 4, m = 2, seq[] = {0, 3, 2, 1}; vector<pair<int,int>> pairs = {{0, 1}, {2, 3}}; solve(n, m, seq, pairs); return 0; }

Input

4, 2, {0, 3, 2, 1}, {{0, 1}, {2, 3}}

Output

2