ধরুন আমাদের একটি শিকড়যুক্ত গাছ আছে। এটি একটি নির্দেশিত গ্রাফ যেমন, এখানে ঠিক একটি নোড (যা রুট) যার জন্য অন্য সব নোড এই নোডের বংশধর, এবং প্রতিটি নোডের ঠিক একটি প্যারেন্ট আছে, রুট নোড ছাড়া। রুটের কোন পিতামাতা নেই৷
প্রদত্ত ইনপুটে একটি নির্দেশিত গ্রাফ যা N নোড সহ একটি মূল গাছ হিসাবে শুরু হয়েছিল (সমস্ত মান অনন্য), একটি অতিরিক্ত নির্দেশিত প্রান্ত যুক্ত করা হয়েছে। যোগ করা প্রান্তটিতে 1 থেকে N থেকে দুটি ভিন্ন শীর্ষবিন্দু বেছে নেওয়া হয়েছে এবং এটি এমন কোনো প্রান্ত ছিল না যা আগে থেকেই ছিল।
গ্রাফ হবে প্রান্তের একটি 2D-অ্যারে। প্রান্তগুলির প্রতিটি উপাদান হল [u, v] এর মতো একটি জোড়া যা একটি নির্দেশিত প্রান্তের সংযোগকারী নোডগুলি u এবং vকে প্রতিনিধিত্ব করে, যেখানে u সন্তান v এর পিতামাতা।
আমাদের এমন একটি প্রান্ত খুঁজে বের করতে হবে যা সরানো যেতে পারে যাতে ফলস্বরূপ গ্রাফটি N নোডের একটি শিকড়যুক্ত গাছ হয়। একাধিক উত্তর থাকতে পারে, প্রদত্ত 2D-অ্যারেতে শেষ যে উত্তরটি আসে তা আমাদের ফিরিয়ে দিতে হবে।
তাই যদি ইনপুট −
এর মত হয়
আউটপুট হবে [2,3]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি ফাংশন getParent() সংজ্ঞায়িত করুন, এটি নোড নেবে, একটি অ্যারে প্যারেন্ট,
- যদি প্যারেন্ট[নোড] -1 এর মত হয়, তাহলে −
- রিটার্ন নোড
- রিটার্ন প্যারেন্ট[নোড] =getParent(অভিভাবক[নোড], অভিভাবক)
- প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
- n :=প্রান্তের আকার
- n + 5 আকারের একটি অ্যারে প্যারেন্ট সংজ্ঞায়িত করুন, এটি -1 দিয়ে পূরণ করুন
- n + 5 আকারের একটি অ্যারে ds সংজ্ঞায়িত করুন -1 দিয়ে এটি পূরণ করুন
- শেষ :=-1, দ্বিতীয় :=- 1, প্রথম :=- 1
- আরম্ভ করার জন্য i :=0, যখন i
- u :=প্রান্ত[i, 0], v :=প্রান্ত[i, 1]
- যদি parent[v] -1 এর সমান না হয়, তাহলে −
- প্রথম :=পিতামাতা[v]
- সেকেন্ড :=i
- নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তিতে যান
- অভিভাবক[v] :=i, parentU :=getParent(u, ds), parentV :=getParent(v, ds)
- যদি parentU parentV এর মত হয়, তাহলে −
- শেষ :=i
- অন্যথায়,
- 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, ]
