मान लीजिए हमारे पास एक जड़ वाला पेड़ है। यह एक निर्देशित ग्राफ है जैसे कि, बिल्कुल एक नोड (जो रूट है) जिसके लिए अन्य सभी नोड्स इस नोड के वंशज हैं, और रूट नोड को छोड़कर प्रत्येक नोड में बिल्कुल एक माता-पिता है। रूट के माता-पिता नहीं हैं।
दिए गए इनपुट में एक निर्देशित ग्राफ जो एन नोड्स (सभी मान अद्वितीय हैं) के साथ जड़ वाले पेड़ के रूप में शुरू हुआ, जिसमें एक अतिरिक्त निर्देशित किनारे जोड़ा गया। जोड़े गए किनारे में 1 से N तक चुने गए दो अलग-अलग कोने हैं, और वह किनारा नहीं था जो पहले से मौजूद था।
ग्राफ़ किनारों का 2डी-सरणी होगा। किनारों का प्रत्येक तत्व [यू, वी] जैसा एक जोड़ा है जो नोड्स यू और वी को जोड़ने वाले एक निर्देशित किनारे का प्रतिनिधित्व करता है, जहां आप बच्चे वी के माता-पिता हैं।
हमें एक किनारा ढूंढना है जिसे हटाया जा सकता है ताकि परिणामी ग्राफ एन नोड्स का जड़ वाला पेड़ हो। कई उत्तर हो सकते हैं, हमें उस उत्तर को वापस करना होगा जो दिए गए 2D-सरणी में अंतिम होता है।
तो अगर इनपुट की तरह है -
आउटपुट [2,3]
. होगाइसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- एक फ़ंक्शन को परिभाषित करें getParent(), यह नोड लेगा, एक सरणी पैरेंट,
- यदि पैरेंट[नोड] -1 के समान है, तो −
- वापसी नोड
- वापसी माता-पिता [नोड] =getParent (माता-पिता [नोड], माता-पिता)
- मुख्य विधि से, निम्न कार्य करें -
- n :=किनारों का आकार
- आकार n + 5 के सरणी पैरेंट को परिभाषित करें, इसे -1 से भरें
- एक सरणी ds आकार n + 5 परिभाषित करें, इसे -1 से भरें
- अंतिम:=-1, दूसरा:=- 1, पहला:=- 1
- इनिशियलाइज़ i :=0 के लिए, जब i
- u:=किनारों[i, 0], v:=किनारों[i, 1]
- यदि माता-पिता[v] -1 के बराबर नहीं है, तो −
- प्रथम:=माता-पिता[v]
- दूसरा:=मैं
- निम्न भाग पर ध्यान न दें, अगले भाग पर जाएं
- अभिभावक[v] :=i, parentU :=getParent(u, ds), parentV :=getParent(v, ds)
- यदि पेरेंटयू, पेरेंटवी के समान है, तो −
- अंतिम:=मैं
- अन्यथा,
- ds[parentV] :=parentU
- वापसी के किनारे[सेकंड]
- वापसी के किनारे[अंतिम]
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
int getParent(int node, vector <int>& parent){
if(parent[node] == -1)return node;
return parent[node] = getParent(parent[node], parent);
}
vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
int n = edges.size();
vector <int> parent(n + 5, -1);
vector <int> ds(n + 5, -1);
int last = -1, second = -1, first = -1;
int u, v;
int parentU, parentV;
for(int i = 0; i < n; i++){
u = edges[i][0];
v = edges[i][1];
if(parent[v] != -1){
first = parent[v];
second = i;
continue;
}
parent[v] = i;
parentU = getParent(u, ds);
parentV = getParent(v, ds);
if(parentU == parentV){
last = i;
}else ds[parentV] = parentU;
}
if(last == -1)return edges[second];
if(second == -1)return edges[last];
return edges[first];
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,2},{1,3},{2,3}};
print_vector(ob.findRedundantDirectedConnection(v));
} इनपुट
{{1,2},{1,3},{2,3}} आउटपुट
[2, 3, ]