मान लीजिए हमारे पास एक अनरूटेड ट्री है; यह एक अदिश ग्राफ है जिसमें कोई चक्र नहीं है। दिया गया इनपुट एक ग्राफ है जो N नोड्स वाले ट्री के रूप में शुरू हुआ था (नोड्स के मान 1 से N तक विशिष्ट हैं), जिसमें एक अतिरिक्त किनारा जोड़ा गया है। जोड़ा गया किनारा 1 से N तक के दो अलग-अलग शीर्षों को जोड़ता है, और यह पहले से मौजूद किनारा नहीं था।
अंतिम ग्राफ को किनारों के 2D-ऐरे के रूप में दिया गया है। edges का प्रत्येक तत्व एक जोड़ी [u, v] है जहां u < v, जो नोड्स u और v को जोड़ने वाले अदिश किनारे को दर्शाता है।
हमें एक ऐसा किनारा ढूंढना है जिसे हटाने पर परिणामी ग्राफ N नोड्स का ट्री बन जाए। कई उत्तर हो सकते हैं, हमें वह उत्तर ढूंढना है जो दिए गए 2D-ऐरे में अंतिम में आता है। उत्तर किनारा [u, v] उसी प्रारूप में होना चाहिए, जहां u < v।
उदाहरण के लिए, यदि इनपुट [[1,2], [2,3], [3,4], [1,4], [1,5]] है, तो आउटपुट [1,4] होगा।
हल करने की विधि
हम यूनियन-फाइंड (डिसजॉइंट सेट यूनियन) का उपयोग करेंगे:
- N = 1000 परिभाषित करें।
- parent और rank सरणियां परिभाषित करें।
getParent()फ़ंक्शन पथ संपीड़न के साथ पैरेंट ढूंढता है।unionn()फ़ंक्शन दो नोड्स को यूनियन करता है, यदि वे पहले से जुड़े हैं तो false लौटाता है।- मुख्य विधि में:
- सभी नोड्स के लिए parent और rank प्रारंभ करें।
- प्रत्येक किनारे के लिए, unionn करें। यदि false लौटाता है, तो वह किनारा उत्तर है।
- उत्तर किनारा लौटाएं।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; void print_vector(vector v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } const int N = 1000; class Solution { public: int parent[N + 5]; int rank[N + 5]; int getParent(int n){ if (parent[n] == -1) return n; return parent[n] = getParent(parent[n]); } bool unionn(int a, int b){ int pa = getParent(a); int pb = getParent(b); if (pa == pb) return false; if (rank[pa] > rank[pb]) { rank[pa] += rank[pb]; parent[pb] = pa; } else { rank[pb] += rank[pa]; parent[pa] = pb; } return true; } vector<int> findRedundantConnection(vector<vector<int>>& edges) { int n = edges.size(); for (int i = 0; i < n; i++) { parent[edges[i][0]] = parent[edges[i][1]] = -1; rank[edges[i][0]] = rank[edges[i][1]] = 1; } vector<int> ans; for (int i = 0; i < n; i++) { int u = edges[i][0]; int v = edges[i][1]; if (!unionn(u, v)) { ans = edges[i]; } } return ans; } }; main(){ Solution ob; vector<vector<int>> v = {{1,2}, {2,3}, {3,4}, {1,4}, {1,5}}; print_vector(ob.findRedundantConnection(v)); }
इनपुट
{{1,2}, {2,3}, {3,4}, {1,4}, {1,5}}
आउटपुट
[1, 4, ]
