ধরুন আমাদের একটি শিকড়বিহীন গাছ আছে; এটি একটি অনির্দেশিত গ্রাফ যার কোন চক্র নেই। প্রদত্ত ইনপুটটি হল একটি গ্রাফ যা N নোড সহ একটি ট্রি হিসাবে শুরু হয়েছে (নোডগুলির মানগুলি 1 থেকে N পর্যন্ত স্বতন্ত্র মান), একটি অতিরিক্ত প্রান্ত যুক্ত করা হয়েছে৷ যোগ করা প্রান্তটিতে 1 থেকে N থেকে দুটি ভিন্ন শীর্ষবিন্দু বেছে নেওয়া হয়েছে এবং এটি এমন কোনো প্রান্ত ছিল না যা আগে থেকেই ছিল।
চূড়ান্ত গ্রাফটি প্রান্তের 2D-অ্যারে হিসাবে দেওয়া হয়েছে। প্রান্তগুলির প্রতিটি উপাদান হল একটি জোড়া [u, v] যেখানে u
আমাদের একটি প্রান্ত খুঁজে বের করতে হবে যা সরানো যেতে পারে যাতে ফলস্বরূপ গ্রাফটি N নোডের একটি গাছ হয়। একাধিক উত্তর থাকতে পারে, প্রদত্ত 2Darray-এ শেষ যে উত্তরটি ঘটে তা আমাদের খুঁজে বের করতে হবে। উত্তর প্রান্ত [u, v] একই বিন্যাসে, u
সুতরাং, যদি ইনপুট হয় [[1,2], [2,3], [3,4], [1,4], [1,5]],
তাহলে আউটপুট হবে [1,4]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
N :=1000
আকারের একটি অ্যারে প্যারেন্ট সংজ্ঞায়িত করুন:N+5।
আকারের একটি অ্যারে র্যাঙ্ক নির্ধারণ করুন:N+5।
একটি ফাংশন getParent() সংজ্ঞায়িত করুন, এটি n,
যদি অভিভাবক [n] -1 এর মত হয়, তাহলে −
ফেরত n
রিটার্ন প্যারেন্ট[n] =getParent(অভিভাবক[n])
একটি ফাংশন unionn() সংজ্ঞায়িত করুন, এটি a, b,
pa :=getParent(a), pb :=getParent(b)
যদি pa pb এর মত হয়, তাহলে −
মিথ্যা ফেরত দিন
যদি rank[pa]> rank[pb] হয়, তাহলে −
র্যাঙ্ক[পা] :=র্যাঙ্ক[পা] + র্যাঙ্ক[পিবি]
পিতামাতা [pb] :=pa
অন্যথায়
র্যাঙ্ক[পিবি] :=র্যাঙ্ক[পিবি] + র্যাঙ্ক[পিএ]
পিতামাতা[pa] :=pb
প্রত্যাবর্তন সত্য
প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
n :=প্রান্ত তালিকার আকার
আরম্ভ করার জন্য i :=0, যখন i
প্যারেন্ট[এজস[i, 0]] :=-1, প্যারেন্ট[এজস[i, 1]] :=- 1
র্যাঙ্ক[এজস[i, 0]] :=-1, র্যাঙ্ক[এজস[i, 1]] :=1
একটি অ্যারে উত্তর সংজ্ঞায়িত করুন
আরম্ভ করার জন্য i :=0, যখন i
u :=প্রান্ত[i, 0]
v :=প্রান্ত[i, 1]
যদি unionn(u, v) শূন্য হয়, তাহলে −
উত্তর :=প্রান্ত[i]
উত্তর ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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, ]
