Number of Provinces
n 個の都市があり、0 から n-1 まで番号が付けられています。行のリストとして n × n の行列 isConnected が与えられます。isConnected[i][j] は、都市 i と都市 j を直接結ぶ道路がある場合は 1、ない場合は 0 です。道路は双方向に通行できるため、行列は対称であり、すべての都市は自分自身とつながっているものとみなします。
省とは、道路がグループの外へ出ておらず、都市同士が直接、またはほかの都市を経由して互いに行き来できる都市のグループです。省の数を返してください。
関数
- isConnectedinteger-2d-array
- n × n 行列。道路が 2 つの都市を直接結んでいる場合は 1
- 戻り値integer
- 州の数
制約
1 ≤ n ≤ 150。ここで、n = isConnected.lengthですisConnected[i].length = nisConnected[i][j]は0または1ですisConnected[i][i] = 1isConnected[i][j] = isConnected[j][i]
例
- 入力
- isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]
- 出力
- 2
- 説明
- 都市 0 は都市 3 への道路があり、都市 1 は都市 2 への道路があります。2 組の間を結ぶ道路はないため、州は 2 つあります。
- 入力
- isConnected = [[1, 1, 0, 0, 0], [1, 1, 1, 0, 0], [0, 1, 1, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1]]
- 出力
- 3
- 説明
- 都市 0 と 2 の間には道路がありませんが、どちらも都市 1 へつながる道路があるため、都市 0、1、2 は 1 つの州を形成します。都市 3 と 4 には道路がまったくなく、それぞれが 1 つの州となるため、州は合計 3 つです。
提出時に隠しテスト+15件
発展問題
各道路は、指定された日に開通します。すべての都市が1つの州に属する最初の日を見つけられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
各都市を点として、対角線上にないそれぞれの
1を2つの点を結ぶ線として描いてください。その図では、州はどのように見えますか？州は連結成分です。2つの都市の間に0があっても、それらが離れているとは限りません。3つ目の都市が両者をつなぐことがあるからです。それ以前の探索で到達していない都市から、新たに探索を開始しなければならない回数を数えましょう。
別の方法：都市ごとに1つずつ、
n個のグループから始め、対角線より上にある各1について、iとjのグループを統合します。異なる2つのグループを統合すると、グループ数は1減ります。経路圧縮を行う素集合データ構造を使うと、各統合をほぼ定数時間で実行できます。
解説
この行列は無向グラフの隣接行列です。都市はノードであり、行 i、列 j の値が 1 なら辺があることを示します。省とは連結成分のことなので、答えは連結成分の数です。注意すべき点は、3つ目の都市を経由して到達できることです。2つの都市の間の値が 0 でも、それらが別々の省に属するとは限りません。未訪問の各都市から探索するか、すべての辺の両端を統合する Union-Find を使えば、行列自体のサイズである O(n²) で連結成分を数えられます。
未訪問のすべての都市からの深さ優先探索
考え方
都市を順番にたどります。これまでの探索でマークされていない都市に出会ったら、すでに数えた州に属していることはありません。各探索で州全体にマークを付けるからです。そこでカウントを1増やし、この都市から到達できるすべての都市にマークを付けます。
到達できる都市を見つけるには、スタックを使います。都市を取り出し、行列のその都市の行を調べ、その行で値が1で、まだマークされていない都市をすべてスタックに入れます。スタックに入れるときにマークも付けます。2つ目の例では、都市0からの探索で都市1がスタックに入り、次に都市1の行によって都市2が追加されます。行0では都市2の値が0であるにもかかわらずです。このように各行をたどることで、ほかの都市を経由してのみつながっている都市も見つけられます。
各都市は1回だけ取り出され、取り出すたびにn個の要素を含む行を調べるため、合計の実行時間はO(n²)です。行列を一度読み取るからです。マークとスタックが保持する都市は最大でもn個なので、追加の空間計算量はO(n)です。
再帰による探索のほうがすっきり書けますが、一本の長い線のような形をした州では、都市ごとに呼び出しが1段ずつネストします。n = 150なら問題ありません。同じコードでも、ノードが10^5個あるグラフでは呼び出しスタックがあふれるため、明示的なスタックを使う習慣を身につけておく価値があります。
アルゴリズム
- すべての都市に訪問済みフラグを作り、カウントを0に設定します。
- 都市を順番に確認し、すでに訪問済みの都市はスキップします。
- 未訪問の都市では、カウントに1を加え、その都市を訪問済みにしてスタックに追加します。
- スタックに都市が残っている間、1つ取り出し、その行にある1で示された未訪問の都市をすべてスタックに追加し、追加する際に訪問済みにします。
- カウントを返します。
def findCircleNum(isConnected):
n = len(isConnected)
seen = [False] * n
provinces = 0
for start in range(n):
if seen[start]:
continue
# Nobody reached this city from an earlier province, so it starts a new one.
provinces += 1
seen[start] = True
stack = [start]
while stack:
city = stack.pop()
row = isConnected[city]
for other in range(n):
# Mark a city when you push it, so it is never pushed twice.
if row[other] == 1 and not seen[other]:
seen[other] = True
stack.append(other)
return provinces経路圧縮とランクによる併合を用いたUnion-Find
考え方
問いを逆から考えてみましょう。まず、都市ごとに1つずつ、n個の州があるとします。行列の1は、2つの都市が同じグループに属することを示します。まだ別々のグループに属しているなら、グループを統合し、数は1つ減ります。最後の道路を処理した後の数が答えです。行列は対称で、対角成分は都市とそれ自身を結ぶので、対角線より上の要素だけを見れば十分です。2つ目の例では、数は5から始まります。(0, 1)の1は都市0と1を統合し（残り4）、(1, 2)の1を処理すると、都市1が都市0のグループに属していることが分かり、都市2もそのグループに加わります（残り3）。都市3と4には対角線より上に1がないため、答えは3です。
素集合データ構造（union-find）は、各グループを木として保持します。parent[c]は1つ上の親を指し、親が自分自身である最上位の都市がグループの根です。2つの都市が同じグループに属するのは、findで両方をたどった先が同じ根になる場合です。2つのグループを統合するには、一方の根をもう一方の根の子にします。
2つのルールによって、木を平坦に保ちます。ランクによる統合では、低い木を高い木の下につなぎます。これにより、高さがhの木には少なくとも2^h個の都市が含まれ、どの経路もlog nより長くなりません。経路圧縮はさらに効率を高めます。findが根を見つけたら、通過した各都市がその根を直接指すようにするため、次回はどの都市から検索しても1ステップで済みます。どちらのルールも使わないと、運悪く長い鎖の都市を順に統合した場合、木が1本の経路になり、各findでO(n)ステップたどることになります。
両方のルールを使うと、各findの償却計算量はO(α(n))です。αは逆アッカーマン関数で、コンピューターが扱えるどんなnに対しても4以下に収まります。行列の読み取りには依然としてO(n²)かかるため、これが全体の計算量です。また、parent配列とrank配列はO(n)の領域を使います。道路が1本ずつ追加される場合に、このデータ構造は特に役立ちます。検索をやり直すことなく、新しい道路を追加するたびに数を最新の状態に保てます。
アルゴリズム
- すべての都市について
parent[c] = cおよびrank[c] = 0に設定し、カウントをnにします。 isConnected[i][j] = 1であるすべての組i < jについて、iとjのルートを見つけます。findでは、ルートまでたどり、その後同じ経路をもう一度たどって、経路上の各都市がルートを直接指すようにします。- ルートが異なる場合は、ランクの低い方のルートをもう一方の下に結合し、ランクが同じならランクに 1 を加え、カウントから 1 を引きます。
- カウントを返します。
def findCircleNum(isConnected):
n = len(isConnected)
parent = list(range(n))
rank = [0] * n
def find(city):
root = city
while parent[root] != root:
root = parent[root]
# Path compression: point every city on the way straight at the root.
while parent[city] != root:
up = parent[city]
parent[city] = root
city = up
return root
provinces = n
for i in range(n):
for j in range(i + 1, n): # the matrix is symmetric, so the upper half is enough
if isConnected[i][j] == 1:
a, b = find(i), find(j)
if a == b:
continue
# Union by rank: hang the shorter tree under the taller one.
if rank[a] < rank[b]:
a, b = b, a
parent[b] = a
if rank[a] == rank[b]:
rank[a] += 1
# Two provinces just became one.
provinces -= 1
return provinces
落とし穴と境界ケース
誤答の多くは、0を2つの都市が別々である証拠として扱ったり、連結成分以外のものを数えたりしています。
- 直接つながる道路だけを確認する。2つ目の例では、都市0と2の間は0ですが、都市1を介して同じ省に属しています。直接つながる道路だけで数えるとこれを見落とします。たとえば、異なる行を数えると、そこでの答えは3ではなく5になります。
- 1の数を数えて2で割る。これは道路の数を数えるものであり、省の数ではありません。3つの都市がすべて互いにつながっている場合、道路は3本で、省は1つです。
- union-findで、2つの根が異なる場合に限らず、1があるたびに数を減らす。すでに統合されたグループ内の道路では、数を変えてはいけません。
- 根ではなく親を比較する。木のより深い位置にある都市がある場合、同じグループに属する2つの都市でも
parent[i] == parent[j]は偽になることがあります。必ずfind(i)とfind(j)を比較してください。 parent[j] = find(i)のように、都市jではなくその根を結びつける。jがすでにグループに属していた場合、そのグループの残りの部分が統合から切り離されます。- 大きなグラフで再帰を使う。再帰的な探索や、ランクによる統合を行わない再帰的な
findは、鎖状のグラフで都市ごとに1段ずつ進みます。都市が150個なら問題ありませんが、10^5個ではスタックオーバーフローになります。
よくある質問4
Number of Provinces の時間計算量はどれくらいですか？
グラフ探索でもUnion-FindでもO(n²)です。どちらもn × n行列の各要素を一度ずつ読み取るためです。Union-Findでは逆アッカーマン関数α(n)の係数が加わりますが、実際の入力では最大でも4です。追加の空間計算量は、訪問済みフラグ、または親配列とランク配列のためにO(n)です。
Number of Provinces には DFS、BFS、union-find のどれを使うべきでしょうか？
3つとも O(n²) 時間で同じ数を返します。行列全体が一度に与えられる場合は、DFS または BFS が最も短く書けます。道路が1本ずつ追加される場合や、2つの都市が同じ省に属しているかどうかにも答える必要がある場合は、Union-find のほうが適しています。新たに探索することなく、各道路や各質問をほぼ定数時間で処理できるためです。
union-findにおける経路圧縮とランクによる併合は、何をするものですか？
ランクによる併合では、2つのグループを統合するときに、短い木を高い木の下に結び付けるため、各木の高さは最大でも log n に保たれます。経路圧縮では、find が通過したすべてのノードの参照先をルートに直接変更するため、後でそれらのノードから検索するときは1ステップで済みます。両方を使うと、m 回の操作からなる任意の列の計算量は O(m α(n)) となり、線形時間に近い動作をします。
「Number of Provinces」と「Number of Islands」はどう違いますか？
どちらも連結成分を数えます。「島の数」ではグラフはグリッドで、各マスの隣接マスは最大4つであり、処理量は O(rows × cols) です。ここではグラフは隣接行列として与えられます。どの都市もほかのどの都市ともつながる可能性があり、1つの都市の隣接都市を列挙するには、n 個の要素からなる行全体を読み取ります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def findCircleNum(isConnected):
# ここにコードを書いてくださいケース1
ケース2
入力
isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]
期待値
2