🤖

LeetCode 1466. Reorder Routes - 隣接リストの作成と幅優先探索

2025/09/27に公開

LeetCode

tech

LeetCode

ポイント

「都市0から他のすべての都市へ移動する際に、向きを変える必要がある道路の最小数を求めること」

これを解決するために、各道路を双方向の隣接リストに変換し、それぞれの向きに「コスト」を持たせる

隣接リストの作成

①有効グラフのため都市0かすべての都市に到達ができない。

connectionsから隣接リストadjancency listに変換をする。
- adj配列は、各都市に「隣接する都市のリスト」を持たせる。
  - adj[0] => [1]は、都市0から到達可能な都市は1ということ。
  - https://qiita.com/taka256/items/a023a11efe17ab097433#グラフの表現

n = 5 # #connections内の最大の都市番号が4のため、nを5に設定
connections = [[0,1],[4,0]]
adj = Array.new(n) { [] }
connections.each do |u, v|
    adj[u] << [v]
end
adj
=> [[[1]], [], [], [], [[0]]]
adj[0]
=> [[1]]

②逆向きのノードを追加することで無向グラフによりすべてのノードに到達可能

n = 5 # #connections内の最大の都市番号が4のため、nを5に設定
connections = [[0,1],[4,0]]
adj = Array.new(n) { [] }
connections.each do |u, v|
    adj[u] << [v]
    adj[v] << [u] # 逆向きのノードを追加
end
adj
=> [[[1], [4]], [[0]], [], [], [[0]]]
adj[0]
=> [[1], [4]]

③反転する道路のコスト設定

ArtificialEdgeを利用して親→子へ移動した場合は、元のエッジは都市0に向かう道路のためコスト0
OriginalEdgeを利用して親→子へ移動した場合は、元のエッジはは都市0から離れる道路のためコスト1

n = 5 # #connections内の最大の都市番号が4のため、nを5に設定
connections = [[0,1],[4,0]]
adj = Array.new(n) { [] }
connections.each do |u, v| # [0,1]の場合、
    adj[u] << [v, 1]  # OriginalEdge: 元の道路の向きは都市0から離れる向きと仮定し、コスト1
    adj[v] << [u, 0]  # ArtificialEdge: 元の道路の逆向きは都市0に向かう向きと仮定し、コスト0
end
adj
=> [[[1, 1], [4, 0]], [[0, 0]], [], [], [[0, 1]]]
adj[0]
=> [[1, 1], [4, 0]]

探索

adj
=> [[[1, 1], [4, 0]], [[0, 0]], [], [], [[0, 1]]]

count = 0
visited = Array.new(n, false)
q = [0]
visited[0] = true

while !q.empty?
    node = q.shift # 幅優先探索。0→1→4の順で処理
    
    adj[node].each do |neighbor, cost| # 
        if !visited[neighbor]
            visited[neighbor] = true
            count += cost
            q << neighbor
        end
    end
end
count
=> 1

Approach

幅優先探索で実装する。

ruby

# @param {Integer} n
# @param {Integer[][]} connections
# @return {Integer}
def min_reorder(n, connections)
    adj = Array.new(n) { [] }
    connections.each do |u, v|
        adj[u] << [v, 1]
        adj[v] << [u, 0]
    end
    
    count = 0
    visited = Array.new(n, false)
    q = [0]
    visited[0] = true

    while !q.empty?
        node = q.shift
        
        adj[node].each do |neighbor, cost|
            if !visited[neighbor]
                visited[neighbor] = true
                count += cost
                q << neighbor
            end
        end
    end
    
    count
end

python

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
      adj = [[] for _ in range(n)]
      for u, v in connections:
        adj[u].append((v, 1))
        adj[v].append((u, 0))
      
      count = 0
      visited = [False] * n
      q = [0]
      visited[0] = True

      while q:
        node = q.pop(0)

        for neighbor, cost in adj[node]:
          if not visited[neighbor]:
            visited[neighbor] = True
            count += cost
            q.append(neighbor)
      return count

typescript

function minReorder(n: number, connections: number[][]): number {
    let adj: [number, number][][] = Array.from({length:n}, () => [])
    for (const [u, v] of connections){
      adj[u].push([v, 1])
      adj[v].push([u, 0])
    }

    let count: number = 0
    let visited: boolean[] = new Array(n).fill(false)
    let q: number[] = [0]
    visited[0] = true

    while(q.length > 0){
      const node = q.shift()

      for (const [neighbor, cost] of adj[node]){
        if (!visited[neighbor]){
          visited[neighbor] = true
          count += cost
          q.push(neighbor)
        }
      }
    }

    return count
};

golang

func minReorder(n int, connections [][]int) int {
	adj := make([][][2]int, n)
	for i := 0; i < n; i++ {
		adj[i] = [][2]int{}
	}
	for _, conn := range connections {
		u, v := conn[0], conn[1]
		adj[u] = append(adj[u], [2]int{v, 1})
		adj[v] = append(adj[v], [2]int{u, 0})
	}

	var count int = 0
	var visited = make([]bool, n)
	var q []int = []int{0}
	visited[0] = true

	for len(q) > 0 {
		node := q[0]
		q = q[1:]

		for _, edge := range adj[node] {
			neighbor, cost := edge[0], edge[1]
			if !visited[neighbor] {
				visited[neighbor] = true
				count += cost
				q = append(q, neighbor)
			}
		}
	}

	return count
}

学習したこと

有向グラフを無向グラフと扱うためにArtificialEdgeを追加して隣接リストを作成する
隣接リストのruby、python、typescript、golangでの作成方法

ruby

    adj = Array.new(n) { [] }
    connections.each do |u, v|
        adj[u] << [v, 1]
        adj[v] << [u, 0]
    end

python

リスト内包表記を利用する

      adj = [[] for _ in range(n)]
      for u, v in connections:
        adj[u].append((v, 1))
        adj[v].append((u, 0))

typescript

    let adj: [number, number][][] = Array.from({length:n}, () => [])
    for (const [u, v] of connections){
      adj[u].push([v, 1])
      adj[v].push([u, 0])
    }

golang

	adj := make([][][2]int, n)
	for i := 0; i < n; i++ {
		adj[i] = [][2]int{}
	}
	for _, conn := range connections {
		u, v := conn[0], conn[1]
		adj[u] = append(adj[u], [2]int{v, 1})
		adj[v] = append(adj[v], [2]int{u, 0})
	}

LeetCode

ポイント

Approach

学習したこと

Discussion