i의 최대값을 찾는 C++ 프로그램

정수 시퀀스 'seq'와 0부터 n - 1까지의 정수를 포함하는 크기가 m인 정수 쌍 '쌍'의 배열이 있다고 가정합니다. 이제 seq[i] = i (0 ≤ i

• 0

의 두 번째 값을 바꿔야 합니다. 여러 번 연산을 수행한 후 seq[i] = i가 되는 i의 최대값을 찾아야 합니다.

따라서 입력이 n = 4, m = 2, seq = {0, 3, 2, 1}, pair = {{0, 1}, {2, 3}}이면 출력은 2가 됩니다.

최대값은 2입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다.

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)

예제

더 나은 이해를 위해 아래 구현을 살펴보겠습니다. −

#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

위 내용은 i의 최대값을 찾는 C++ 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!