মান লিজিয়ে, n সংখ্যক ভেরটেক্সযুক্ত একটি গ্রাফ দেওয়া আছে। ভেরটেক্সগুলো ১ থেকে n পর্যন্ত নম্বর করা আছে এবং 'edges' অ্যারেতে দেওয়া এজগুলো দ্বারা সংযুক্ত। প্রতিটি ভেরটেক্সের একটি 'x' মান আছে যা ১ থেকে n পর্যন্ত, যা 'values' অ্যারেতে দেওয়া আছে। এখন আমাদের লক্ষ্য হলো গ্রাফ থেকে সুপার ভেরটেক্সগুলো বের করা। একটি ভেরটেক্স i কে 'সুপার ভেরটেক্স' বলা হবে যদি ভেরটেক্স ১ থেকে i পর্যন্ত সবচেয়ে ছোট পথে i-তম ভেরটেক্সের 'x' মানের সমান কোনো ভেরটেক্স না থাকে। আমরা এই শর্ত পূরণ করা সব ভেরটেক্স প্রিন্ট করব।
যেমন, ইনপুট হলে n = 5, values = {1, 2, 2, 1, 3}, edges = {{1, 2}, {2, 3}, {2, 3}, {2, 4}, {4, 5}}, তবে আউটপুট হবে 1 3 4 5।
ভেরটেক্স ২ বাদে সব ভেরটেক্স শর্ত পূরণ করে। তাই ভেরটেক্স ২ বাদ দেওয়া হয়েছে।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
vertexVal, frq, chk অ্যারে সংজ্ঞায়িত করুন আকার: 100005। vcti অ্যারে সংজ্ঞায়িত করুন আকার 200005। একটি dfs() ফাংশন সংজ্ঞায়িত করুন, যা j, k গ্রহণ করবে: if frq[vertexVal[j]] == 0, তবে: chk[j] := 1 (frq[vertexVal[j]] ১ বাড়িয়ে) vcti[j]-র প্রতিটি মান a জন্য: if a != k, তবে: dfs(a, j) (frq[vertexVal[j]] ১ কমিয়ে) i := 0 দিয়ে আরম্ভ করুন, i < n হলে, (i ১ বাড়িয়ে) করুন: vertexVal[i] := values[i] i := 0 দিয়ে আরম্ভ করুন, i < n হলে, (i ১ বাড়িয়ে) করুন: a := edges[i]-র ১ম মান b := edges[i]-র ২য় মান vcti[a]-র শেষে b যোগ করুন vcti[b]-র শেষে a যোগ করুন dfs(1, 0) i := 1 দিয়ে আরম্ভ করুন, i <= n হলে, (i ১ বাড়িয়ে) করুন: if chk[i] নন-জিরো, তবে: print(i)
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বুঝতে:
#include <bits/stdc++.h> using namespace std; int n; int vertexVal[100005], frq[100005], chk[100005]; vector<int> vcti[200005]; void dfs(int j, int k){ if (frq[vertexVal[j]] == 0) chk[j] = 1; frq[vertexVal[j]]++; for (auto a : vcti[j]) { if (a != k) dfs(a, j); } frq[vertexVal[j]]--; } void solve(int values[], vector<pair<int, int>> edges){ for (int i = 0; i < n; i++) vertexVal[i] = values[i]; for (int i = 0; i < n; i++){ int a, b; a = edges[i].first; b = edges[i].second; vcti[a].push_back(b); vcti[b].push_back(a); } dfs(1, 0); for (int i = 1;i <= n; i++){ if (chk[i]) cout<< i <<endl; } } int main() { n = 5; int values[] = {1, 2, 2, 1, 3}; vector<pair<int, int>> edges = {{1, 2}, {2, 3}, {2, 3}, {2, 4}, {4, 5}}; solve(values, edges); return 0; } ইনপুট
5, {1, 2, 2, 1, 3}, {{1, 2}, {2, 3}, {2, 3}, {2, 4}, {4, 5}} আউটপুট
1 3 4 5
