मान लीजिए n वर्टेक्स वाला एक ग्राफ दिया गया है। वर्टेक्स 1 से n तक संख्याबद्ध हैं और 'edges' सरणी में दी गई एज्स से जुड़े हैं। प्रत्येक वर्टेक्स का एक 'x' मान है जो 1 से n के बीच होता है, यह 'values' सरणी में दिया गया है। हमें ग्राफ में सुपर वर्टेक्स खोजने हैं। एक वर्टेक्स i को 'सुपर वर्टेक्स' कहा जाता है यदि वर्टेक्स 1 से i तक के सबसे छोटे पथ में कोई ऐसा वर्टेक्स न हो जिसका 'x' मान i-वें वर्टेक्स के समान हो। हमें ऐसे सभी वर्टेक्स प्रिंट करने हैं।
उदाहरण के लिए, यदि इनपुट है n = 5, values = {1, 2, 2, 1, 3}, edges = {{1, 2}, {2, 3}, {2, 3}, {2, 4}, {4, 5}}, तो आउटपुट 1 3 4 5 होगा।
वर्टेक्स 2 को छोड़कर हर वर्टेक्स मानदंड को पूरा करता है। इसलिए वर्टेक्स 2 बाहर है।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
आकार 100005 के सरणी vertexVal, frq, chk परिभाषित करें
आकार 200005 का सरणी vcti परिभाषित करें
एक फंक्शन dfs() परिभाषित करें, जो j, k लेता है:
यदि frq[vertexVal[j]] == 0, तो:
chk[j] := 1
frq[vertexVal[j]] बढ़ाएँ
vcti[j] में प्रत्येक मान a के लिए:
यदि a != k, तो:
dfs(a, j)
frq[vertexVal[j]] घटाएँ
i := 0 से n-1 तक:
vertexVal[i] := values[i]
i := 0 से n-1 तक:
a := edges[i] का पहला मान
b := edges[i] का दूसरा मान
b को vcti[a] के अंत में डालें
a को vcti[b] के अंत में डालें
dfs(1, 0)
i := 1 से n तक:
यदि chk[i] शून्येतर है, तो:
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
