मान लीजिए हमारे पास पूर्णांकों का एक क्रमपरिवर्तन 'seq' और पूर्णांक युग्मों की एक सरणी 'pairs' है जिसका आकार m है और जिसमें 0 से n-1 तक के पूर्णांक हैं। अब हम seq पर निम्न ऑपरेशन जितनी बार संभव हो उतनी बार करते हैं ताकि seq[i] = i (0 ≤ i < n) अधिकतम हो।
- हमें एक पूर्णांक j चुनना है जहाँ 0 ≤ j < m, और फिर seq[pairs[j] का पहला मान] और seq[pairs[j] का दूसरा मान] को स्वैप करना है।
हमें ऑपरेशन को कई बार करने के बाद seq[i] = i के लिए i का अधिकतम मान ज्ञात करना है।
उदाहरण के लिए, यदि इनपुट है n = 4, m = 2, seq = {0, 3, 2, 1}, pairs = {{0, 1}, {2, 3}}, तो आउटपुट 2 होगा।
अधिकतम संभव मान 2 है।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
N := 100
आकार N के सरणी tp, vtmp, vis परिभाषित करें
एक फंक्शन dfs() परिभाषित करें जो j, k लेता है:
tp[j] := k
j को vtmp[k] के अंत में डालें
vis[j] में प्रत्येक मान b के लिए:
यदि tp[b] != 0, तो जारी रखें
dfs(b, k)
res := 0
i := 0 से n-1 तक:
यदि seq[i] == i, तो res बढ़ाएँ
i := 0 से m-1 तक:
a := pairs[i] का पहला मान
b := pairs[i] का दूसरा मान
b को vis[a] के अंत में डालें
a को vis[b] के अंत में डालें
idx := 1
i := 0 से n-1 तक:
यदि tp[i] == 0, तो:
dfs(i, idx)
vtmp[idx] में प्रत्येक तत्व j के लिए:
यदि tp[seq[j]] == idx और seq[j] != j, तो:
res बढ़ाएँ
idx बढ़ाएँ
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
