Redundant Connection
ネットワークは木として始まりました。n 個のノードがあり、1 から n まで番号が付けられ、サイクルを含まない無向辺 n-1 本でつながっていました。その後、直接つながっていない2つのノードの間に辺が1本追加されたため、リスト edges には現在 n 本の辺が含まれ、サイクルがちょうど1つあります。
その辺を1本削除すると、残りの n-1 本の辺が再び木を形成するような辺を返してください。該当する辺が複数ある場合は、edges 内で最後に現れるものを、そこに書かれているとおりの組 [a, b] で返してください。
関数
- edgesinteger-2d-array
- n 本の無向辺。それぞれは、1 から番号が付けられたノードのペア [a, b] です
- 戻り値integer-array
- edges 内で最後に現れるサイクルの辺（そこに記載されているとおり）
制約
3 ≤ n ≤ 5000（n = edges.lengthの場合）edges[i] = [a, b]で、1 ≤ a, b ≤ nかつa ≠ b- どの辺も、どちらの向きであっても、2回現れることはありません。
- 辺はすべての
n個のノードを接続し、ちょうど1つのサイクルを持ちます。
例
- 入力
- edges = [[1, 2], [1, 3], [2, 3]]
- 出力
- [2, 3]
- 説明
- 3つの辺は三角形 1, 2, 3 を形成するため、そのうちどれか1つを取り除くと木が残ります。
[2, 3]はリストの最後にあります。
- 入力
- edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
- 出力
- [1, 4]
- 説明
- サイクルは 1, 2, 3, 4, 1 です。辺
[1, 5]はその上にありません。これを取り除くと、ノード 5 が切り離されます。4つのサイクル辺のうち、[1, 4]が最後に現れます。
発展問題
辺が有向で、元のグラフが根付き木だった場合、追加された辺によってノードに2つの親ができるとき、どの辺を削除しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
辺を取り除いても、
n個のノードすべてが連結されたままでなければなりません。グラフを二つに分断せずに、どの辺を取り除けますか？サイクル上の辺だけです。各辺にはサイクルを一周する別の経路があり、それ以外の辺はすべて、グラフのある部分につながる唯一の辺です。したがって、答えはリストの最後にあるサイクル上の辺です。
リストの順序どおりに、辺を
n個の別々のグループに追加します。両端がすでに同じグループに属している最初の辺がサイクルを閉じ、それ以外のサイクル上の辺はすべてその前に追加されています。Union-Findを使えば、1回の走査でその辺を見つけられます。
解説
辺を削除したときに木が残るのは、その辺がグラフの唯一のサイクル上にある場合に限られます。したがって、答えはリストの中で最後に現れるサイクル上の辺です。Union-findを使えば1回の走査で見つけられます。辺を順に追加し、両端がすでにつながっている最初の辺が答えです。
各辺を取り除いてみましょう。最後の辺から始めます。
正しいが、最大のテストでは終わらない
考え方
1 本の辺を取り除き、残りの n-1 本の辺が木を形成するか確認します。n 個のノードと n-1 本の辺がある場合、ノード 1 からの探索ですべての n 個のノードに到達できれば、木を形成します。リストの末尾から辺を試すと、条件を満たす最初の削除が最も後ろの辺になります。各辺のインデックスを隣接リストに保存しておけば、探索中に削除した辺を飛ばせるため、何も再構築せずに済みます。
試すたびに O(n) の探索が必要で、試行回数は最大 n 回です。n = 5000 のとき、最大 2.5 × 10^7 ステップになります。
アルゴリズム
- 各隣接ノードについて、そこへつながる辺のインデックスを保持する隣接リストを作成します。
- 最後のインデックスから0まで
skipを順に変え、ノード1から探索し、インデックスがskipの辺を無視します。 - 探索で到達したノードの数を数えます。
- すべての
n個に到達した場合は、edges[skip]を返します。
def findRedundantConnection(edges):
n = len(edges)
# graph[x] holds (neighbour, index of the edge) for every edge at node x.
graph = [[] for _ in range(n + 1)]
for i, (u, v) in enumerate(edges):
graph[u].append((v, i))
graph[v].append((u, i))
# Try leaving out each edge, the last one first.
for skip in range(n - 1, -1, -1):
# Without edge skip, can node 1 still reach all n nodes?
seen = [False] * (n + 1)
seen[1] = True
stack = [1]
reached = 1
while stack:
node = stack.pop()
for nxt, i in graph[node]:
if i != skip and not seen[nxt]:
seen[nxt] = True
reached += 1
stack.append(nxt)
# n-1 edges that connect n nodes form a tree.
if reached == n:
return edges[skip]
return []葉を取り除く
考え方
辺が1本だけのノードである葉は、サイクル上には存在できません。サイクルは各ノードに入り、そこから出ていくためです。葉を取り除くと隣接ノードが葉になることがあるので、葉がなくなるまで取り除き続けます。残るのはサイクルそのものです。サイクル上の各ノードには、サイクルを構成する2本の辺が残るためです。2つ目の例では、ノード5が取り除かれ、ノード1には2本の辺が残り、ノード1から4までが残ります。
残った2つのノードを結ぶ辺は、どれもサイクルの辺です。サイクル上のノード間に2本目のリンクがあると、別のサイクルができてしまうためです。そこで、edgesを末尾から調べ、両端がどちらも残っている最初の辺を返します。
アルゴリズム
- 隣接リストを作成し、各ノードの次数を数えます。
- 次数が1のすべてのノードをスタックにプッシュします。
- 葉をポップして次数を0に設定し、残った隣接ノードの次数を減らします。その次数が1になったら、その隣接ノードをプッシュします。
- スタックが空になったとき、次数が0より大きいノードがサイクルを形成します。
edgesを末尾から走査し、両端が残っている最初の辺を返します。
def findRedundantConnection(edges):
n = len(edges)
graph = [[] for _ in range(n + 1)]
degree = [0] * (n + 1)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
degree[u] += 1
degree[v] += 1
# A node with one edge cannot lie on the cycle. Remove it, and repeat.
stack = [x for x in range(1, n + 1) if degree[x] == 1]
while stack:
leaf = stack.pop()
degree[leaf] = 0
for nxt in graph[leaf]:
if degree[nxt] > 0:
degree[nxt] -= 1
if degree[nxt] == 1:
stack.append(nxt)
# Only the cycle is left. Its edge that comes last in the list is the answer.
for u, v in reversed(edges):
if degree[u] > 0 and degree[v] > 0:
return [u, v]
return []Union-find：ループを閉じる最初の辺
考え方
辺をリストの順に追加し、どのノード同士がつながっているかを追跡します。サイクルが閉じるまでは、各辺はそれまでに経路のない2つの部分を結びます。両端がすでにつながっている最初の辺によって、サイクルが閉じます。サイクルのほかの辺はその前に追加されているため、サイクルを閉じる辺が最後に現れる辺です。2つ目の例では、[1, 4]によってノード1と4がすでにつながっていることがわかり、[1, 5]は読み込まれません。
union-findは1つの配列parentを保持します。ノードからポインターをたどると、その部分のルートにたどり着きます。小さい部分を大きい部分の下に結合し、findの実行中にノードのポインターを祖父母ノードに向けることで、チェーンを短く保ちます。各操作の償却計算量はO(α(n))となります。ここでαはアッカーマン関数の逆関数であり、実際の入力ではどのような場合でも4以下です。
アルゴリズム
- 1 から
nまでの各ノードの親を自分自身に設定し、parent[x] = xとして、サイズを 1 にします。 edgesを順番に確認します。[u, v]について、uのルートとvのルートを調べます。- ルートが一致する場合、
[u, v]はサイクルを閉じます。そのまま返します。 - 一致しない場合、大きい方の集合が小さい方を吸収します。大きい方のルートを小さい方のルートの親にし、サイズを合計します。
def findRedundantConnection(edges):
n = len(edges)
parent = list(range(n + 1)) # every node starts as its own group
size = [1] * (n + 1)
def find(x):
# Walk up to the root, halving the path on the way.
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for u, v in edges:
a, b = find(u), find(v)
# u and v are already connected: this edge closes the cycle.
if a == b:
return [u, v]
# Hang the smaller group under the larger one.
if size[a] < size[b]:
a, b = b, a
parent[b] = a
size[a] += size[b]
return []
落とし穴と境界ケース
- リストの末尾の辺を返すこと。2つ目の例ではそれは
[1, 5]であり、それを取り除くとノード5が切り離されます。 - 取り除いた後、先頭から走査すること。これにより最も早いサイクルの辺が返され、2つ目の例では
[1, 2]です。 - ペアをソートしたり、順序を逆にしたりすること。リストに
[3, 1]が含まれている場合は、[1, 3]ではなく[3, 1]を返してください。 - ノード0から
n-1までの配列サイズにすること。ノードの番号は1から始まるため、ノードnにはn+1個の要素を持つ配列が必要です。 - サイクルを再帰的にたどること。5000個すべてのノードを通る場合があり、これはPythonのデフォルトの再帰制限の5倍です。そのため、
findでは明示的なスタックとループを使用してください。
よくある質問3
冗長な接続の時間計算量はどれくらいですか？
Union-findはn本の辺を1回走査するだけで解決します。計算時間はO(n · α(n))で、実際にはα(n)は最大でも4です。空間計算量はO(n)です。葉を取り除く方法もO(n)です。削除する要素ごとに新たに探索を行うと、O(n²)のコストがかかります。
木を残すには、どの辺を取り除けばよいでしょうか？
ちょうどサイクル上の辺です。それぞれの辺の両端の間には、サイクルの残りの部分を通る別の経路があるため、その辺を取り除いてもグラフは連結されたままです。それ以外の辺は、グラフの2つの部分を結ぶ唯一の接続であり、それを取り除くと両者は分断されます。
Redundant ConnectionはDFSで解けますか？
はい。各辺を追加する前に、これまでに追加した辺をたどって一方の端点から探索します。もう一方の端点にすでに到達できる場合、最初に見つかった辺が答えです。これには辺ごとに O(n)、合計で O(n²) かかりますが、union-find なら同じ問いにほぼ定数時間で答えられます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def findRedundantConnection(edges):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
edges = [[1, 2], [1, 3], [2, 3]]
期待される出力
[2, 3]