सी ++ में अनावश्यक कनेक्शन

मान लीजिए हमारे पास एक बिना जड़ वाला पेड़ है; यह एक अप्रत्यक्ष ग्राफ है जिसमें कोई चक्र नहीं है। दिया गया इनपुट एक ग्राफ है जो एन नोड्स के साथ एक पेड़ के रूप में शुरू हुआ (नोड्स के मान 1 से एन तक के अलग-अलग मान हैं), एक अतिरिक्त किनारे के साथ। जोड़े गए किनारे में 1 से N तक चुने गए दो अलग-अलग कोने हैं, और वह किनारा नहीं था जो पहले से मौजूद था।

अंतिम ग्राफ किनारों की 2D-सरणी के रूप में दिया गया है। किनारों का प्रत्येक तत्व एक जोड़ी है [u, v] जहां u

हमें एक किनारा ढूंढना है जिसे हटाया जा सकता है ताकि परिणामी ग्राफ एन नोड्स का एक पेड़ हो। कई उत्तर हो सकते हैं, हमें उस उत्तर को खोजना होगा जो दिए गए 2Darray में सबसे अंत में आता है। उत्तर का किनारा [यू, वी] उसी प्रारूप में होना चाहिए, जिसमें यू <वी.

इसलिए, यदि इनपुट [[1,2], [2,3], [3,4], [1,4], [1,5]],

तो आउटपुट [1,4]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एन:=1000

• आकार के सरणी पैरेंट को परिभाषित करें:N+5.

• आकार की एक सरणी रैंक परिभाषित करें:N+5.

• getParent() फ़ंक्शन को परिभाषित करें, इसमें n लगेगा,

• अगर माता-पिता [एन] -1 के समान है, तो -

  • वापसी n

• वापसी माता-पिता [एन] =माता-पिता प्राप्त करें (माता-पिता [एन])

• एक फ़ंक्शन को परिभाषित करें Unionn(), इसमें a, b,

  लगेगा

• पा :=getParent(a), pb :=getParent(b)

• अगर पा, पीबी के समान है, तो -

  • झूठी वापसी

• अगर रैंक [पा]> रैंक [पीबी], तो −

  • रैंक [पीए]:=रैंक [पीए] + रैंक [पीबी]

  • माता-पिता [पीबी] :=पा

• अन्यथा

  • रैंक [पीबी]:=रैंक [पीबी] + रैंक [पीए]

  • माता-पिता [पीए]:=पीबी

• सही लौटें

• मुख्य विधि से, निम्न कार्य करें -

• n :=किनारों की सूची का आकार

• इनिशियलाइज़ i :=0 के लिए, जब i

  • माता-पिता [किनारों [i, 0]]:=-1, माता-पिता [किनारों [i, 1]]:=- 1

  • रैंक [किनारों [i, 0]]:=-1, रैंक [किनारों [i, 1]]:=1

• एक सरणी को परिभाषित करें ans

• इनिशियलाइज़ i :=0 के लिए, जब i

  • आप:=किनारों[i, 0]

  • वी:=किनारों[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, ]