19. Number of Connected Components in an Undirected Graph

読了目安約2分

Graph / LeetCode 323 (Medium) — 隣接リストと探索で連結成分を数える。Premium 限定。

この章の目次

問題

LeetCode 323. Number of Connected Components in an Undirected Graph（Medium / カテゴリ: Graph）

LeetCode Premium 限定です。問題の要点は次の要約の通りです。

0 から n - 1 の番号がついた n 個の頂点と、無向辺のリスト edges が与えられます。 edges の各要素 [a, b] は、頂点 a と頂点 b を双方向につなぐ辺です。辺をたどって行き来できる頂点のまとまりを連結成分と呼びます。グラフ全体の連結成分の個数を返します。

例を挙げます。 n = 5, edges = [[0, 1], [1, 2], [3, 4]] なら、{0, 1, 2} と {3, 4} の 2 つに分かれるので答えは 2 です。辺が 1 本もなければ全頂点が孤立し、答えは n です。

無料で読める類題として LeetCode 547. Number of Provinces があります。入力が隣接行列に変わるだけで、数えるものは同じです。

考え方

ヒント 1

Number of Islands の島数えと同じ構図です。未訪問の頂点を見つけるたびに成分を 1 つ数え、そこから届く頂点をすべて訪問済みにします。

ヒント 2

まず辺のリストから、頂点ごとの隣の一覧（隣接リスト）を作ります。訪問済みを覚える配列を持ち、未訪問の頂点を始点に深さ優先探索（DFS）か幅優先探索（BFS）で到達できる頂点を塗りつぶします。 Union-Find でも解けますが、探索で十分です。

Swift 実装のポイント

隣接リストは var adj: [[Int]] = Array(repeating: [], count: n) で作り、辺ごとに両方向へ追加します。
スタックで書く DFS は while let v = stack.popLast() が定番です。再帰でも書けます。
始点の列挙は for start in 0..<n where !visited[start] と書けます。

模範解答

Swift
class Solution {
    func countComponents(_ n: Int, _ edges: [[Int]]) -> Int {
        var adj: [[Int]] = Array(repeating: [], count: n)
        for edge in edges {
            adj[edge[0]].append(edge[1])
            adj[edge[1]].append(edge[0])
        }
        var visited = Array(repeating: false, count: n)
        var count = 0
        for start in 0..<n where !visited[start] {
            count += 1
            var stack = [start]
            visited[start] = true
            while let v = stack.popLast() {
                for next in adj[v] where !visited[next] {
                    visited[next] = true
                    stack.append(next)
                }
            }
        }
        return count
    }
}

計算量: O(n + e)（e は辺の数。各頂点と各辺を定数回ずつ処理します）。