Number of Provinces
都市が n 個あり、0 から n-1 まで番号が付いています。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つです。
発展問題
各道路は指定された日に開通します。すべての都市が1つの州に属する最初の日を見つけられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
各都市を点として描き、対角線上にないそれぞれの
1を、2つの点を結ぶ線として描きます。その図では、州はどのように見えるでしょうか？州とは連結成分のことです。2つの都市の間に0があっても、それらが離れているとは限りません。3つ目の都市が両者をつなぐことがあるからです。それ以前の検索で到達できなかった都市から、新たに検索を開始しなければならない回数を数えましょう。
別の方法:
n個のグループから始め、各都市に1つずつ割り当て、対角線より上にある1ごとにiとjのグループを統合します。異なる2つのグループを統合すると、個数は1つ減ります。経路圧縮を行うUnion-Findを使えば、各統合をほぼ定数時間で実行できます。
解説
この行列は無向グラフを表します。都市はノードで、それぞれの1は辺です。州は連結成分であり、2つの都市の間に0があっても、3つ目の都市が両方をつないでいれば、それらは分断されません。未訪問の各都市から探索するか、すべての辺に対してUnion-Findを使うことで、O(n²)で連結成分の数を数えられます。
未訪問の各都市からの深さ優先探索
考え方
未マークの都市は、すでに数えた州に属することはありません。各探索で州全体にマークを付けるためです。したがって、その都市から新しい州が始まります。探索は行列の行に沿って進みます。2つ目の例では、都市 0 からの探索で都市 1 に到達し、続いて都市 1 の行から都市 2 に到達しますが、行 0 では都市 2 の値は 0 です。
各都市は一度だけ取り出され、n 個の要素からなる行を読み取るため、行列を一度読み取ります。時間計算量は O(n²) です。マークとスタックには最大で n 個の都市が入るため、追加の空間計算量は O(n) です。
アルゴリズム
- 各都市に訪問済みフラグを作り、カウントを 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
考え方
n 個の州から始めます。各都市に 1 つずつ割り当てます。対角線より上にある 1 は、2 つの都市が同じグループに属することを示します。グループが異なる場合は、それらを結合して数を 1 減らします。2 つ目の例では、数は 5 から始まり、(0, 1) によって都市 0 と 1 が結合され、(1, 2) によって都市 2 がそのグループに加わり、州は 3 つ残ります。
Union-find では、各グループを木として格納します。parent[c] は 1 つ上のノードを指し、find が 2 つの都市をたどって同じルートに到達すると、それらは同じグループに属します。何もしなければ、結合によって長い経路ができ、各 find が O(n) ステップをたどることになります。ランクによる結合では、短い木を高い木の下につなぐため、経路の長さは log n を超えません。経路圧縮では、find が通過した各都市がルートを直接指すようにします。これらを組み合わせると、各 find の償却計算量は O(α(n)) となり、実用上 α(n) は 4 以下です。
アルゴリズム
- 各都市について
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
落とし穴と境界ケース
- 直接つながっている道路だけを信頼すること。2つ目の例では、都市0と2の間に0があるにもかかわらず、同じ州に属しています。
- 1の数を数えて2で割ること。互いにすべてつながっている3つの都市には、3本の道路と1つの州があります。
- union-findでは、2つの根が異なる場合だけでなく、1があるたびにカウントを減らすこと。
parent[i]とparent[j]を比較すること。同じグループに属する2つの都市でも、一方がより深い位置にある場合、親は異なることがあります。find(i)とfind(j)を比較してください。parent[j] = find(i)のように、都市j自体をつなぐこと。jがすでにグループに属していた場合、そのグループの残りの部分はマージから取り残されます。
よくある質問3
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 です。「この2つの都市は同じ省に属していますか」のような質問にも多数答える必要がある場合は、Union-find のほうが適しています。各質問にほぼ定数時間で答えられるためです。
「Number of Provinces」と「Number of Islands」はどう違いますか？
どちらも連結成分を数えます。Number of Islands では、グラフは格子で、各マスには最大4つの隣接マスがあり、計算量は O(rows × cols) です。ここではグラフは隣接行列です。どの都市もほかのどの都市ともつながる可能性があり、ある都市の隣接都市を列挙するには、n 個の要素からなる行全体を読み取ります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def findCircleNum(isConnected):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]
期待される出力
2