素集合 (Union-Find) で木に 1 本だけ足された余分な道を見つける

輪の無いつながり (木) に 1 本だけ道が足されて輪ができた道の並びから、外すと木に戻る道を見つけます。道を順につなぎながら、両端がもう同じまとまりにいる道を素集合ですぐ見つける練習です。

海外で定番の問題リスト 4 本には入っていません

問題

島に n 個の村があり、1 から n の番号が付いています。もとは n - 1 本の道で全部の村がつながり、どの 2 つの村のあいだにも、通り方がちょうど 1 通りだけありました (輪の無いつながり、木です)。そこへ道が 1 本だけ足され、輪ができました。

道の並び edges を受け取ります。edges[i] = [a, b] は、村 a と村 b を結ぶ両向きの道です。n 本の道のうち、1 本外すと、また全部の村がつながった輪の無い形に戻る道を返す関数を書いてください。

そのような道がいくつかあるときは、edges でいちばん後ろにある道を返します
道は edges に書いてある通りの向き ([a, b] の a と b の順) で返します
n は 3 以上 1000 以下で、edges の長さは n です。同じ 2 つの村を結ぶ道は 2 本ありません。自分の村へ戻る道もありません

入力と出力の例

例 1

1、2、3 が輪になっています。輪の 3 本のどれを外しても木に戻りますが、いちばん後ろの [3, 1] を返します。

edges = [[1, 2], [2, 3], [3, 1]]

[3, 1]

例 2

輪は 2、3、4 の 3 本です。4 と 5 の道は輪に入っていないので、外すと 5 が離れてしまいます。輪の中でいちばん後ろの [4, 2] を返します。

edges = [[2, 3], [4, 5], [3, 4], [1, 2], [4, 2]]

[4, 2]

例 3

輪は 1、2、3、4 を回る 4 本で、[4, 1] はその 4 本のうち edges でいちばん後ろにあります。そのあとの [4, 5] は輪に入りません。

edges = [[1, 2], [3, 4], [2, 3], [4, 1], [4, 5]]

[4, 1]

面接での聞かれ方

面接では、短く次のように渡されることが多いです。

「木に辺を 1 本足したグラフが辺の並びで渡されます。外すと木に戻る辺を返してください。答えが複数あれば、入力で最後の物を返します」
書き終えると「find と union は、それぞれどれだけかかりますか？」と、素集合の工夫 (経路の圧縮) を聞かれます
「辺に向きがあったら？」と広げて聞かれることもあります (別の、もっと難しい問題になります)

答えが複数あるときにどれを返すかを最初に確かめておくと、なぜ「最初に輪を作った道」を返せばよいかを説明できます。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「グラフ探索と幅優先探索」に、この型の要点を表とコードでまとめています。

グラフ探索は、つながりを近い順か奥からたどります。迷路、最短の手数、講座を受ける順のような問題が同じ形です。

まず考える手順

段 1

道を 1 本ずつ外してみて、残りが全部つながっているかを毎回たどって調べる書き方がまず浮かびます。外す道が n 本、調べるのが O(n) で、全体で O(n²) です。

段 2

道を前から 1 本ずつ足していくことを考えます。足す前から、両端の村がすでにほかの道でつながっているなら、その道は輪を作ります。輪は 1 つしか無いので、輪を作るのは輪の道のうち edges でいちばん後ろの道です。それより前の輪の道は、足した時点ではまだ輪を閉じていません。つまり、最初に見つかる「両端がもうつながっている道」が答えです。

段 3

「2 つの村がもうつながっているか」と「2 つのまとまりをつなぐ」を速くこなすのが、素集合 (Union-Find) です。村ごとに親を持ち、親をたどった先の根がまとまりの代表です。2 つの村の根が同じなら、もうつながっています。違えば、片方の根の親をもう片方の根にして、まとまりをつなぎます。

段 4

根をたどるときに、通った村の親を 1 つ飛ばしで付け替えると (経路の圧縮)、木が浅くなり、次から速くたどれます。これで 1 回の操作はほぼ定数の時間になります。

解答

Python

def redundant_edge(edges):
    n = len(edges)
    p = list(range(n + 1))

    def find(x):
        while p[x] != x:
            p[x] = p[p[x]]
            x = p[x]
        return x

    for a, b in edges:
        ra = find(a)
        rb = find(b)
        if ra == rb:
            return [a, b]
        p[ra] = rb
    return []

JavaScript

function redundantEdge(edges) {
  const n = edges.length;
  const p = [];
  for (let i = 0; i <= n; i++) {
    p.push(i);
  }
  const find = (x) => {
    while (p[x] !== x) {
      p[x] = p[p[x]];
      x = p[x];
    }
    return x;
  };
  for (const [a, b] of edges) {
    const ra = find(a);
    const rb = find(b);
    if (ra === rb) {
      return [a, b];
    }
    p[ra] = rb;
  }
  return [];
}

Go

func redundantEdge(
	edges [][]int,
) []int {
	p := make([]int, len(edges)+1)
	for i := range p {
		p[i] = i
	}
	find := func(x int) int {
		for p[x] != x {
			p[x] = p[p[x]]
			x = p[x]
		}
		return x
	}
	for _, e := range edges {
		ra := find(e[0])
		rb := find(e[1])
		if ra == rb {
			return e
		}
		p[ra] = rb
	}
	return []int{}
}

村の番号は 1 から n なので、親の並びは 0 番を使わずに n + 1 個用意しています。最後の return [] には、問題の決まり (輪が必ず 1 つある) のもとでは届きません。

計算量

時間は O(n α(n)) です。α は、n がどれだけ大きくても 5 を超えない、とても伸びの遅い関数で、ほぼ O(n) と見てかまいません。経路の圧縮だけでも、実際にはほぼこの速さで動きます
使う記憶は O(n) です。村ごとの親の並びです

よくある間違い

輪の道を全部探してから選ぶ。輪を作った最初の道が、輪の道のうち edges でいちばん後ろの道です。順に足して最初に見つかった道を、そのまま返せます
根ではなく村そのものをつなぐ。 p[a] = b とすると、a のまとまりのほかの村が置き去りになり、つながりを見誤ります。つなぐのは 2 つの根です
親の並びを n 個で作る。番号が 1 から n なので、n 番の村が並びの外になります
道の向きを入れ替えて返す。 [3, 1] を [1, 3] で返すと、決まりと違います。受け取った道をそのまま返します

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def redundant_edge(edges: list[list[int]]) -> list[int]:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(redundant_edge([[1, 2], [2, 3], [3, 1]]))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します