C++で解く「冗長な接続 II」— 余分な有向エッジの検出アルゴリズム

問題の概要

根付き木（rooted tree）とは、次のような性質を持つ有向グラフのことです。すべてのノードがその子孫となる「根（ルート）」がちょうど1つ存在し、根以外のすべてのノードは親をちょうど1つ持ちます。根だけは親を持ちません。

入力として与えられるのは、N個のノード（ノードの値はすべて一意）からなる根付き木に、有向エッジを1本追加した有向グラフです。追加されたエッジは1からNまでの中から選ばれた異なる2つの頂点を結ぶものであり、元の木には存在しなかったエッジです。

グラフは2次元配列edgesで表現されます。edgesの各要素は[u, v]というペアで、ノードuからノードvへ向かう有向エッジ（uはvの親）を表します。

求めるのは、1本のエッジを取り除いたときに、残りのグラフがN個のノードからなる根付き木になるようなエッジです。答えが複数存在する場合は、与えられた2次元配列の中で最も後ろに出現するものを返します。

例えば、次のような入力が与えられたとします。

エッジは [1,2]、[1,3]、[2,3] の3本です。この場合、出力は [2,3] となります。ノード3には2本の親エッジ（1→3 と 2→3）が入っており、[2,3] を取り除くことで有効な根付き木が復元できるためです。

解法のアプローチ

この問題は、Union-Find（素集合データ構造）と各ノードの親情報の記録を組み合わせることで効率的に解けます。手順は以下の通りです。

• getParent()関数を定義する：引数としてnodeと配列parentを受け取ります。
  • parent[node]が-1の場合は、nodeをそのまま返します。
  • それ以外の場合は、parent[node] = getParent(parent[node], parent)を返します（経路圧縮により計算量を削減できます）。
• メインのメソッドで以下を実行します：
  • n := edgesのサイズとします。
  • サイズn + 5の配列parentを定義し、すべて-1で初期化します。
  • サイズn + 5の配列dsを定義し、すべて-1で初期化します。
  • last := -1、second := -1、first := -1と初期化します。
  • iを0からn未満まで1ずつ増やしながら、以下を繰り返します。
    • u := edges[i][0]、v := edges[i][1]とします。
    • parent[v]が-1でない場合（ノードvにすでに親が存在する場合）：
      • first := parent[v]（先に見つかった親エッジのインデックス）
      • second := i（後に見つかった親エッジのインデックス）
      • 以降の処理をスキップして次の反復へ進みます。
    • parent[v] := i とし、parentU := getParent(u, ds)、parentV := getParent(v, ds)を計算します。
    • parentUとparentVが等しい場合（サイクルが検出された場合）：
      • last := i とします。
    • そうでない場合：
      • ds[parentV] := parentU として2つの集合を統合します。
• 最後に、3つの場合に分けて答えを返します：
  • lastが-1の場合（サイクルが存在しない場合）：edges[second]を返します。
  • secondが-1の場合（重複する親が存在しない場合）：edges[last]を返します。
  • どちらも存在する場合：edges[first]を返します。

実装例

以下のC++実装を見ると、アルゴリズムの動作をより深く理解できるでしょう。

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

このアルゴリズムの計算量は、Union-Findの経路圧縮によりほぼO(N)に抑えられ、N個のノードからなる大規模なグラフでも効率的に動作します。