Graph Valid Tree
0からn-1まで番号が付けられたn個のノードと、無向辺のリストedgesが与えられます。各ペア[a, b]は、ノードaとノードbを結びます。
辺によってすべてのn個のノードが1つの木になる場合、つまり、すべてのノードから他のすべてのノードに到達でき、閉路がない場合はtrueを返します。それ以外の場合はfalseを返します。
関数
- ninteger
- ノードの数。0 から n-1 まで番号が付けられている
- edgesinteger-2d-array
- 無向辺。それぞれがペア [a, b] です
- 戻り値boolean
- 辺がすべての n 個のノードを1つの木に結合している場合は true、そうでない場合は false
制約
2 ≤ n ≤ 1041 ≤ edges.length ≤ 5000edges[i] = [a, b]で、0 ≤ a, b ≤ n-1かつa ≠ b- どの辺も、どちらの方向であっても二度現れることはありません。
例
- 入力
- n = 5edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
- 出力
- true
- 説明
- ノード0はノード1、2、3につながっており、ノード4はノード1から伸びています。4本の辺がループなしですべての5つのノードをつないでいるので、これは木です。
- 入力
- n = 5edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
- 出力
- false
- 説明
- 辺
[1, 2]、[2, 3]、[1, 3]は、1、2、3、1 のループを形成します。5つのノード上の5つの辺は、木が持てる辺の数より1つ多いです。
- 入力
- n = 4edges = [[0, 1], [1, 2], [2, 0]]
- 出力
- false
- 説明
- 辺は3本あり、これは
n-1ですが、0、1、2、0というループを形成しており、ノード3には辺がまったくありません。
発展問題
グラフが木でない場合、木にするには辺をいくつ削除し、いくつ追加する必要がありますか？ 1回の走査で両方を数えられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
木ではない小さなグラフをいくつか描いてください。失敗する方法は2つだけです。それは何ですか？
グラフが木でないのは、サイクルがあるか、一部のノードがつながっていない場合です。
n個のノードを持つ木の辺の数はちょうどn-1本であり、辺がちょうどn-1本なら、この2つの問題は必ず同時に起こります。そこで、まず辺の数を確認し、次に2つの問題のどちらか一方を確認します。各ノードが単独で始まるとします。各辺について、その両端がすでに同じグループに属しているかどうかを確認します。属している場合、その辺は閉路を形成します。属していない場合は、両方のグループを結合します。Union-find を使うと、その問いにほぼ定数時間で答えられます。
解説
木は連結であり、サイクルがありません。辺がちょうど n-1 本ある場合、この2つは同じ条件です。このようなグラフは、サイクルがない場合に限り連結です。したがって、まず辺の数を確認し、その後、連結性を一度調べるか、すでにつながっている2つのノードを結ぶ辺をunion-findで検出します。
すべての辺の前にパスを検索する
正しいが、最大のテストでは終わらない
考え方
辺を1本ずつ追加します。[u, v]を追加する前に、これまでに追加した辺をたどってuから探索します。vに到達できる場合、新しい辺は2つのノード間の2つ目の経路となり、2つ目の例の[1, 3]のように閉路を作ります。閉路を作る辺がなければ、グラフは森であり、ノード0から最後に探索すれば、1つの木かどうかが分かります。
各チェックでは、そこまでに追加されたグラフ全体を探索します。辺が順番に追加される、5001個のノードからなるパスでは、探索で訪れるノード数は1 + 2 + ... + 5000となり、約1250万です。
アルゴリズム
- 各ノードの隣接リストを空の状態で用意します。
- 各辺
[u, v]について、uから、これまでに追加された辺をたどって探索します。vに到達した場合は、falseを返します。 - そうでなければ、両端のリストに辺を追加します。
- 最後に、ノード 0 からの探索ですべての
n個のノードに到達できるかどうかを返します。
def reachable(graph, start):
# Every node a search from start can reach, using the edges added so far.
seen = [False] * len(graph)
seen[start] = True
stack = [start]
while stack:
node = stack.pop()
for nxt in graph[node]:
if not seen[nxt]:
seen[nxt] = True
stack.append(nxt)
return seen
def validTree(n, edges):
graph = [[] for _ in range(n)]
for u, v in edges:
# A path from u to v already exists, so this edge closes a cycle.
if reachable(graph, u)[v]:
return False
graph[u].append(v)
graph[v].append(u)
# No cycle anywhere. A tree also needs every node reachable from node 0.
return all(reachable(graph, 0))辺を数えてから、1回だけ検索する
考え方
n 個の独立したノードから始めて、辺を1本ずつ追加します。各辺は、2つのグループをつないでグループを1つ減らすか、グループ内に追加されてサイクルを閉じます。グループが1つになるには、n-1 回つなぐ必要があります。そのため、n-1 本未満の辺ではグラフを連結できず、それより多い辺があればサイクルが閉じます。2つ目の例では、5個のノードに対して辺が5本あるため、個数だけで条件を満たしません。
辺がちょうど n-1 本のとき、すべての辺がグループをつないだ場合、つまりサイクルを閉じる辺がなかった場合に限り、グラフは1つのグループになります。したがって、個数が適切であれば、連結性だけを確認します。ノード0から探索を1回行い、n 個すべてのノードに到達できなければなりません。3つ目の例では、到達できるのは0、1、2だけです。m = n-1 のとき、リストの処理と探索の計算量は O(n) です。
アルゴリズム
edges.lengthがn-1でない場合は、falseを返します。- 隣接リストを作成し、各辺を両端のノードの下に格納します。
- ノード0をスタックにプッシュし、訪問済みとしてマークします。
- ノードをポップし、まだ訪問していないすべての隣接ノードをプッシュします。プッシュする際に、訪問済みとしてマークし、カウントします。
- カウントが
nと等しいかどうかを返します。
def validTree(n, edges):
# A tree on n nodes has exactly n-1 edges.
if len(edges) != n - 1:
return False
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
# With n-1 edges, the graph is a tree exactly when it is connected.
seen = [False] * n
seen[0] = True
stack = [0]
reached = 1
while stack:
node = stack.pop()
for nxt in graph[node]:
if not seen[nxt]:
seen[nxt] = True
reached += 1
stack.append(nxt)
return reached == n辺の数え上げとUnion-Find
考え方
Union-find は、探索を行わずに各辺についてサイクルができるかどうかを判定します。最初は各ノードがそれぞれ独立したグループに属しています。辺 [u, v] について、両端の根を見つけます。根が異なる場合、その辺は2つの部分をつなぐので、グループを統合します。根が同じ場合、u と v はすでにつながっており、その辺によってサイクルが閉じます。すべての n-1 本の辺がグループを統合すると、n 個のグループは最終的に1つになり、木になります。
親ノードの連鎖を短く保つためのルールが2つあります。統合時には、小さいグループの根を大きいグループの根の下につなぐため、ノードが10^4個あっても連鎖が13ステップを超えることはありません。find の実行中は、たどった各ノードの親を祖父母ノードに付け替えます。これらを組み合わせると、m 回の操作にかかるコストは O(m α(n)) になります。ここで、逆アッカーマン関数 α は、この場合最大でも4です。空間計算量は O(n) です。
アルゴリズム
edges.lengthがn-1でない場合は、falseを返します。- すべてのノードについて、
parent[x] = xとし、グループサイズを 1 に設定します。 - 各辺
[u, v]について、uとvからそれぞれ親をたどって根まで進み、通過した各ノードの親をその祖父母に設定します。 - 根が同じ場合は、
falseを返します。 - 根が異なる場合は、小さい方のグループの根をもう一方の根に結び付け、そのサイズを加算します。
- すべての辺が 2 つのグループを統合した場合は、
trueを返します。
def validTree(n, edges):
# A tree on n nodes has exactly n-1 edges.
if len(edges) != n - 1:
return False
parent = list(range(n)) # every node starts as its own group
size = [1] * n
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)
# The two ends are already joined: this edge closes a cycle.
if a == b:
return False
# Hang the smaller group under the larger one.
if size[a] < size[b]:
a, b = b, a
parent[b] = a
size[a] += size[b]
# n-1 merges with no cycle turn the n groups into one.
return True
落とし穴と境界ケース
- サイクルだけを調べる。6つのノードに3本の独立した辺がある場合、サイクルはないものの、連結成分は3つになる。
- 辺の数だけを調べる。3つ目の例には
n-1本の辺があるが、ループ0、1、2が、ノード3に必要な辺を使ってしまっている。 - 各辺を片方の端点にだけ保存する。
[1, 0]もノード0と1をつないでいるのに、ノード0からの探索ではノード1を見つけられない。 - 親ノードをスキップしない深さ優先のサイクル判定。すべての辺が、たどってきたノードへまっすぐ戻るため、「訪問済みの隣接ノードに遭遇した」という条件がすべての木で成立してしまう。
- 長い経路を再帰でたどる。5001個のノードが一直線に並ぶと、呼び出しの深さは5000になり、Pythonのデフォルト上限である1000を超える。明示的なスタックを使う。
よくある質問3
Graph Valid Tree の時間計算量は何ですか？
深さ優先探索では O(n + m)、union-find では O(n + m α(n)) です。どちらも最初に辺の数を確認するため、数が正しくないグラフは探索を行う前に拒否されます。ここで m は辺の数です。
ノードが n 個ある木の辺が n-1 本なのはなぜですか？
1つのノードから木を成長させ、他のノードを1つずつ追加します。新しいノードには必ず辺が1本だけつながります。辺がなければ切り離され、2本あればサイクルができてしまいます。したがって、n個のノードにはn-1本の辺が必要です。
無向グラフ内のサイクルをどのように検出しますか？
union-find では、両端がすでに同じルートを共有している辺はサイクルを形成します。深さ優先探索では、サイクルとは、到着元のノード以外で訪問済みの隣接ノードのことなので、各ノードの親を記録します。union-find では、親も隣接リストも必要ありません。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def validTree(n, edges):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
n = 5 edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
期待される出力
true