問題
n 個のlinks をlinks[i][j] が 1 なら
linksは n 行 n 列で、値は 数の 0 か 1 です links[i][i]はいつも 1 です。 links[i][j]とlinks[j][i]はいつも同じです - n は 1 以上 200 以下です
入力と出力の例
例 1
町 0 と
入力
links = [[1, 1, 0, 0],
[1, 1, 0, 0],
[0, 0, 1, 1],
[0, 0, 1, 1]]出力
2例 2
道が 1 本も
入力
links = [[1, 0, 0, 0],
[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 0, 0, 1]]出力
4例 3
町 0 と
入力
links = [[1, 0, 0, 1, 0],
[0, 1, 0, 1, 0],
[0, 0, 1, 0, 0],
[1, 1, 0, 1, 0],
[0, 0, 0, 0, 1]]出力
3面接での聞かれ方
面接では、
- 「つながりの
表から、 グループが いくつあるかを 数えてください」 - 書き終えた
あとに 「深さ優先でも 解けますが、 素集合で 書くと 何が うれしいですか？」 「道が あとから 1 本ずつ 増えていくなら、 どう 数え直しますか？」と 続けて 聞かれます - 「
findを速く する ための 工夫を 2 つ挙げてください」と、 素集合の 中身を 聞かれる こともあります
表が
アルゴリズムのチートシートの「グラフ探索と幅優先探索」に、この型の要点を表とコードでまとめています。
まず
段 1
まずは、
段 2
ここでは、
段 3
代表をfind は、
段 4
つなぐfind 1 回のfind は
解答
Python
Python
def find(parent, x):
top = x
while parent[top] != top:
top = parent[top]
while parent[x] != top:
up = parent[x]
parent[x] = top
x = up
return top
def count_groups(links):
n = len(links)
parent = list(range(n))
sz = [1] * n
groups = n
for i in range(n):
for j in range(i):
if links[i][j] == 0:
continue
a = find(parent, i)
b = find(parent, j)
if a == b:
continue
if sz[a] < sz[b]:
a, b = b, a
parent[b] = a
sz[a] += sz[b]
groups -= 1
return groupsJavaScript
JavaScript
function find(parent, x) {
let top = x;
while (parent[top] !== top) {
top = parent[top];
}
while (parent[x] !== top) {
const up = parent[x];
parent[x] = top;
x = up;
}
return top;
}
function countGroups(links) {
const n = links.length;
const parent = [];
const sz = [];
for (let i = 0; i < n; i++) {
parent.push(i);
sz.push(1);
}
let groups = n;
links.forEach((row, i) => {
row.forEach((v, j) => {
if (j >= i || v === 0) {
return;
}
let a = find(parent, i);
let b = find(parent, j);
if (a === b) return;
if (sz[a] < sz[b]) {
[a, b] = [b, a];
}
parent[b] = a;
sz[a] += sz[b];
groups--;
});
});
return groups;
}Go
Go
func find(
parent []int, x int,
) int {
top := x
for parent[top] != top {
top = parent[top]
}
for parent[x] != top {
up := parent[x]
parent[x] = top
x = up
}
return top
}
func countGroups(
links [][]int,
) int {
n := len(links)
parent := make([]int, n)
sz := make([]int, n)
for i := range parent {
parent[i] = i
sz[i] = 1
}
groups := n
for i := 0; i < n; i++ {
for j := 0; j < i; j++ {
if links[i][j] == 0 {
continue
}
a := find(parent, i)
b := find(parent, j)
if a == b {
continue
}
if sz[a] < sz[b] {
a, b = b, a
}
parent[b] = a
sz[a] += sz[b]
groups--
}
}
return groups
}parent はsz はfind の 1 つ目のtop をj は i よりforEach のreturn は、
計算量
- 時間は O(n² α(n)) です。
表のます目を 半分ほど 見て、 道ごとに findを 2 回呼びます。α(n) は、 経路の 圧縮と 大きさで つなぐ 工夫を 両方使った ときの find1 回の手間で、 n が 現実の どんな 大きさでも 4 を 超えない、 ほぼ 一定の値です - 使う
記憶は O(n) です。 親の 並びと 大きさの 並びだけです - 表を
読むだけで n² かかるので、 段 1 の 幅優先と 時間の 大きさは 同じです。 素集合の 強みは、 道が 1 本ずつ 増えていく 場面でも、 そのつど数え直さずに 済むところです
よく
- 代表を
探さずに、 町その ものをつなぐ。 parent[j] = iと町を 直接つなぐと、 j が すでに 別の まとまりの 途中に いた とき、 そのまとまりの 残りが 切り離されます。 つなぐのは、 必ず findで見つけた 根どうしです - 同じまとまりなのに、
数を減らす。 根が 同じかを 確かめずに 数を 1 減らすと、 輪に なった 道で 減らしすぎます。 根が 違う ときだけ、 つないで 減らします - 町の
数を 根以外で足す。 szは根の 物だけが 正しい 値です。 つないだあとに、 下へ 入れた 側の 大きさを、 上に なった 根へ足します
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での
書き始める
「幅優先で
まとまりを 塗っても O(n²) で 解けますが、 ここでは 素集合で 書きます。 最初は 町の 数だけまと まりが あり、 道を 見る たびに 両端の 根を 探して、 違えば 小さい ほうを 大きい ほうの 下へつなぎ、 数を 1 減らします。 findは経路を 圧縮するので、 全体で O(n² α(n)) です。」
書き終えたら、
「例 3 で
たどります。 最初は 5 つです。 町 0 と 町 3 の 道で、 根が 違うので つないで 4 つに なります。 町 1 と 町 3 の 道で、 町 3 の 根は 町 0 なので、 町 1 を そこへつないで 3 つです。 残りは 自分 自身との 1 だけなので、 答えは 3 です。」