C++での冗長接続II

根付いた木があるとします。これは、他のすべてのノードがこのノードの子孫であるノード（ルート）が1つだけ存在し、ルートノードを除くすべてのノードが親を1つだけ持つような有向グラフです。ルートには親がいません。

与えられた入力で、N個のノード（すべての値は一意）を持つルートツリーとして開始され、1つの有向エッジが追加された有向グラフ。追加されたエッジには、1からNまで選択された2つの異なる頂点があり、既存のエッジではありませんでした。

グラフはエッジの2D配列になります。エッジの各要素は、ノードuとvを接続する有向エッジを表す[u、v]のようなペアです。ここで、uは子vの親です。

結果のグラフがNノードのルートツリーになるように、削除できるエッジを見つける必要があります。複数の回答がある可能性があります。指定された2D配列で最後に発生した回答を返す必要があります。

したがって、入力が-

出力は[2,3]

これを解決するには、次の手順に従います-

• 関数getParent（）を定義します。これにより、配列の親であるノードが取得されます。
• parent [node]が-1と同じ場合、-
  • リターンノード
• return parent [node] =getParent（parent [node]、parent）
• メインの方法から、次の手順を実行します-
• n：=エッジのサイズ
• サイズn+5の配列の親を定義し、これに-1を入力します
• サイズn+5の配列dsを定義します。これを-1で埋めます
• 最後：=-1、2番目：=-1、最初：=-1
• iを初期化する場合：=0、i
• u：=エッジ[i、0]、v：=エッジ[i、1]
• parent [v]が-1に等しくない場合、-
  • 最初：=親[v]
  • 秒：=i
  • 次の部分を無視し、次の反復にスキップします
• parent [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, ]