資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律學C++程式找出i的最大值
假設，我們有一個整數的排列'seq'和一個大小為m的整數對陣列'pairs'，其中包含整數0到n - 1。現在，我們對seq執行以下操作儘可能多次，以便使seq[i] = i（0 ≤ i < n）最大化。
我們必須選擇一個整數j，其中0 <= j < m，然後交換seq[pair[j]的第一個值]和seq[pair[j]的第二個值]
我們必須找出i的最大值，以便在執行多次操作後seq[i] = i。
因此，如果輸入類似於n = 4，m = 2，seq = {0, 3, 2, 1}，pairs = {{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;
}輸入
4, 2, {0, 3, 2, 1}, {{0, 1}, {2, 3}}輸出
2
更新於: 2022年2月25日
143 次瀏覽
廣告