Home > Backend Development > C++ > C++ program to find the maximum value of i

C++ program to find the maximum value of i

PHPz
Release: 2023-09-15 20:09:08
forward
1079 people have browsed it

C++ program to find the maximum value of i

Suppose we have an integer sequence 'seq' and an array of integer pairs 'pairs' of size m, containing the integers 0 to n - 1. Now, we perform the following operations on seq as much as possible so that seq[i] = i (0 ≤ i

  • We must choose an integer j where 0

We must find the maximum value of i such that seq[i] = i after performing the operation multiple times.

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

The maximum possible value is 2.

To solve this problem, we will follow the following 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)
Copy after login

Example

Let us see the implementation below for 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;
}
Copy after login

Input

4, 2, {0, 3, 2, 1}, {{0, 1}, {2, 3}}
Copy after login

Output

2
Copy after login

The above is the detailed content of C++ program to find the maximum value of i. For more information, please follow other related articles on the PHP Chinese website!

Related labels:
source:tutorialspoint.com
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template