C++での冗長接続

根なしの木が1つあるとします。これは、サイクルのない1つの無向グラフです。指定された入力は、N個のノード（ノードの値は1からNまでの範囲の個別の値）を持つツリーとして開始され、1つのエッジが追加されたグラフです。追加されたエッジには、1からNまで選択された2つの異なる頂点があり、既存のエッジではありませんでした。

最終的なグラフは、エッジの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が必要です。

• parent [n]が-1と同じ場合、-

  • nを返す

• return parent [n] =getParent（parent [n]）

• 関数unionn（）を定義します。これには、a、b、

  が必要です。

• pa：=getParent（a）、pb：=getParent（b）

• paがpbと同じ場合、-

  • falseを返す

• ランク[pa]>ランク[pb]の場合、-

  • ランク[pa]：=ランク[pa]+ランク[pb]

  • 親[pb]：=pa

• それ以外の場合

  • ランク[pb]：=ランク[pb]+ランク[pa]

  • parent [pa]：=pb

• trueを返す

• メインの方法から、次のようにします-

• n：=エッジリストのサイズ

• 初期化i：=0の場合、i

  • parent [edges [i、0]]：=-1、parent [edges [i、1]]：=-1

  • ランク[エッジ[i、0]]：=-1、ランク[エッジ[i、1]]：=1

• 配列を定義します

• 初期化i：=0の場合、i

  • u：=エッジ[i、0]

  • v：=エッジ[i、1]

  • unionn（u、v）がゼロの場合、-

    • ans：=edge [i]

• ansを返す

例

理解を深めるために、次の実装を見てみましょう-

#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, ]