C++で解く「冗長接続（Redundant Connection）」問題 ― Union-Findによる効率的な実装

問題概要

まず、根のない木（unrooted tree）について考えてみましょう。これは閉路（サイクル）を持たない無向グラフのことです。

入力として与えられるのは、もともと N 個のノードを持つ木（ノードの値は 1 から N までの重複しない整数）に、余分な辺を 1 本追加したグラフです。追加された辺は 1 ～ N の中から選ばれた 2 つの異なる頂点を結び、既存の辺とは重複しません。

最終的なグラフは 2 次元配列 edges として渡されます。edges の各要素はペア [u, v]（u < v）であり、ノード u と ノード v を結ぶ無向辺を表します。

求めるのは、その辺を取り除けば残りのグラフが N ノードの木になるような辺です。答えが複数存在する場合は、与えられた 2 次元配列の中で最後に現れるものを返す必要があります。返す辺も [u, v]（u < v）という同じ形式で表します。

入力例

たとえば、入力が [[1,2], [2,3], [3,4], [1,4], [1,5]] の場合：

このとき出力は [1,4] となります。辺 [1,4] を削除すると、グラフは再び閉路のない木に戻るためです。

解法のアプローチ：Union-Find（素集合データ構造）

この問題は Union-Find（Disjoint Set Union） と呼ばれるデータ構造を使うことで効率的に解けます。基本的な考え方はシンプルです。

辺を順番に処理していき、ある辺の両端点がすでに同じ連結成分に属している場合、その辺を追加すると閉路が形成されます。つまり、その辺こそが「冗長な接続」だということになります。

アルゴリズムの手順

• N := 1000 とする
• サイズ N+5 の配列 parent を定義する
• サイズ N+5 の配列 rank を定義する
• 関数 getParent(n) を定義する：
  • parent[n] が -1 なら、n をそのまま返す（n が根であることを意味する）
  • そうでなければ parent[n] = getParent(parent[n]) を返す（経路圧縮により探索を高速化）
• 関数 unionn(a, b) を定義する：
  • pa := getParent(a)、pb := getParent(b) を計算する
  • pa == pb の場合は false を返す（すでに同じグループ＝閉路が発生）
  • rank[pa] > rank[pb] の場合：
    • rank[pa] := rank[pa] + rank[pb]
    • parent[pb] := pa
  • それ以外の場合：
    • rank[pb] := rank[pb] + rank[pa]
    • parent[pa] := pb
  • true を返す（マージ成功）
• メイン処理では以下を行う：
  • n := edges リストのサイズ
  • i = 0 から n 未満まで繰り返し：
    • parent[edges[i][0]] と parent[edges[i][1]] を -1 に初期化
    • rank[edges[i][0]] と rank[edges[i][1]] を 1 に初期化
  • 配列 ans を定義する
  • 再び i = 0 から n 未満まで繰り返し：
    • u := edges[i][0]、v := edges[i][1]
    • unionn(u, v) が false を返した場合：
      • ans := edges[i]（この辺が冗長な辺）
  • ans を返す

すべての辺を最後まで走査することで、仮に複数の候補があっても、配列上で最後に見つかった冗長な辺が自動的に ans に残る仕組みになっています。

C++による実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> 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]

まとめ

この手法の計算量は、経路圧縮とランク（サイズ）によるマージのおかげで、ほぼ O(N α(N))（α はアッカーマン関数の逆関数で事実上定数）と非常に高速です。閉路検出が必要なグラフ問題全般に応用できる強力なパターンなので、ぜひ覚えておきましょう。