মান লিজিয়ে, একটি পূর্ণসংখ্যার পারমুটেশন 'seq' এবং m আকারের পূর্ণসংখ্যা পেয়ারের অ্যারে 'pairs' আছে যাতে 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।
সর্বোচ্চ সম্ভাব্য মান হলো ২।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
N := 100 tp অ্যারে সংজ্ঞায়িত করুন আকার: N। vtmp, vis অ্যারে সংজ্ঞায়িত করুন আকার N। dfs() ফাংশন সংজ্ঞায়িত করুন, যা j, k গ্রহণ করবে: tp[j] := k j কে vtmp[k]-র শেষে যোগ করুন vis[j]-র প্রতিটি b মান জন্য: if tp[b] != 0, তবে: continue dfs(b, k) res := 0 i := 0 থেকে n-1 পর্যন্ত: if seq[i] == i, তবে: res ১ বাড়িয়ে i := 0 থেকে m-1 পর্যন্ত: a := pairs[i]-র ১ম মান b := pairs[i]-র ২য় মান vis[a]-র শেষে b যোগ করুন vis[b]-র শেষে a যোগ করুন idx := 1 i := 0 থেকে n-1 পর্যন্ত: if tp[i] == 0, তবে: dfs(i, idx) vtmp[idx]-র প্রতিটি j উপাদানের জন্য: if tp[seq[j]] == idx এবং seq[j] != j, তবে: res ১ বাড়িয়ে idx ১ বাড়িয়ে 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
2
