問題

問題文

N 頂点 M 辺の有向グラフ G があります。 頂点には 1,2,…,N と番号が振られています。 各 i (1≤i≤M) について、i 番目の有向辺は頂点 xi​ から yi​ へ張られています。G は有向閉路を含みません。

G の有向パスのうち、最長のものの長さを求めてください。 ただし、有向パスの長さとは、有向パスに含まれる辺の本数のことです。

解法

誤った解法

与えられた条件から、各頂点を通ったときの最大値を保持し、それの最大を取れば計算できそうに思える。

func run() interface{} {
	n, m := readInt(), readInt()

	// 経路読込
	sli := make([][]int, m)
	for i := 0; i < m; i++ {
		sli[i] = readSli(2)
	}

	dp := make([]int, n)

	for i := 0; i < m; i++ {
		from, to := sli[i][0]-1, sli[i][1]-1
		path := dp[from]
		// 最大値を保持
		dp[to] = Max(dp[to], path+1)
	}
	max := 0
	for i := 0; i < n; i++ {
		max = Max(dp[i], max)
	}

	return max
}

しかし、この方法だと入力値の順序が変わった場合、対応できない

入力例３の順序変更

5 8
4 3  ( これが前にきている）
1 3
5 3
2 3
2 4
5 2
5 1
1 4
> 2

dpでは、ある状態を処理するときは、その状態に遷移する状態はすべて処理しきっている必要がある。
（上のやつだと、４→３への状態を処理する時、〇→４になる状態はすべて処理する必要があるが、あとで2 4, 1 4 が出てきており、条件を満たさない）
この問題は有向閉路を含まないグラフ（DAG)であるため、適切に経路を選べば上記の条件を満たすことができ、計算前にソートを実行する（トポロジカルソート）

トポロジカルソート

参考資料

定義：
点u から点v に到達できることをR(u, v)とする。u ≠ v かつ R(u, v)ならば、
u が v よりも先に現れるように一列に並び変えること

ノードを矢印がついたまま一直線にならべたとき、矢印の向きがすべて同じになるように並べること

トポロジカルソートの方法

1. 入次数0の頂点vを発見する。

2. 頂点vを配列の末尾に追加する。

3. 有向グラフから頂点vと、その頂点から出ている辺をすべて削除する

この方法で可能だが、１．を行うために毎回すべての頂点を調べると計算量がとんでもないことになるため、入次数を確認するのは３．で辺を削除した隣接した頂点のみで十分であることに着目する

	//１． 既に処理可能なノードをキューに入れる
	var queue []*Node
	for _, node := range graph {
		if node.deg == 0 {
			queue = append(queue, node)
		}
	}

	// キューの先頭から処理していく
	for i := 0; i < len(queue); i++ {
		node := queue[i]
		// ３．グラフから頂点を削除する
		delete(graph, node.self)

		for idx := range node.next {
			// ２．矢印の先の入次数を減らす
			(graph[idx].deg)--
			// １．入次数が0のとき、キューに追加する
			if graph[idx].deg == 0 {
                // ２．配列の末尾に追加する
				queue = append(queue, graph[idx])
			}
		}
	}

これでdpで計算を行うための条件を満たせるので、最大値を計算できる

コード（AC)

type Node struct {
	self int              // 自身の番号
	next map[int]struct{} // 隣接している、矢印の先の頂点の番号
	deg  int              // 入次数
}

func run() interface{} {
	n, m := readInt(), readInt()

	// グラフの初期化
	graph := make(map[int]*Node)
	for i := 1; i <= n; i++ {
		graph[i] = &Node{next: map[int]struct{}{}, deg: 0, self: i}
	}
	// 経路の読込
	for i := 0; i < m; i++ {
		from, to := readInt(), readInt()
		graph[from].next[to] = struct{}{}
		graph[to].deg++
	}

	// トポロジカルソート実行----------------------
	// 既に処理可能なノードをキューに入れる
	var queue []*Node
	for _, node := range graph {
		if node.deg == 0 {
			queue = append(queue, node)
		}
	}

	// キューの先頭から処理していく
	for i := 0; i < len(queue); i++ {
		node := queue[i]
		// グラフから頂点を削除する
		delete(graph, node.self)

		for idx := range node.next {
			// 矢印の先の入次数を減らす
			(graph[idx].deg)--
			// 入次数が0のとき、キューに追加する
			if graph[idx].deg == 0 {
				queue = append(queue, graph[idx])
			}
		}
	}
	// トポロジカルソート終了----------------------

	// 最大値を保持し、計算する
	dp := make([]int, n)
	for i := 0; i < n; i++ {
		node := queue[i]
		for j := range node.next {
			dp[j-1] = Max(dp[j-1], dp[node.self-1]+1)
		}
	}

	// 全ての中での最大値を取得する
	ans := 0
	for i := 0; i < n; i++ {
		ans = Max(ans, dp[i])
	}
	return ans
}

別解

メモ化再帰をつかっても計算可能

var dp []int
var xy map[int][]int

func run() interface{} {
	n, m := readInt(), readInt()

	// x: from node
	// y: to nodes list
	xy = make(map[int][]int, n)
	for i := 0; i < m; i++ {
		x, y := readInt()-1, readInt()-1
		xy[x] = append(xy[x], y)
	}

	// メモ＋最大値の保存に利用するため、-1で初期化
	dp = initSliceAs(n, -1)

	ans := 0
	for x := 0; x < n; x++ {
		ans = Max(ans, calculate(x))
	}
	return ans
}

func calculate(x int) int {
	if dp[x] > -1 {
		return dp[x]
	}

	max := 0
	for _, v := range xy[x] {
		max = Max(calculate(v)+1, max)
	}
	dp[x] = max
	return max
}

1. ans = Max(ans, calculate(1))

2. max = Max(calculate(6) +1, 0)

3. max = Max(calculate(7) +1,0)

4. max = Max(calculate(8), 0) = 1

5.  3の値が確定　(max = 2)

6. ２の値が確定  (max = 3)

7.  1の値が確定 (ans = Max(0, 3) = 3)

8. ans = Max(ans, calculate(2))

9. max = Max(calculate(5) +1, 0)

10. max = Max(calculate(1) +1, 0)  = 4

11. 9の値が確定 (max = 5)

12.  8 の値が確定 ( ans = Max(3, 5) = 5 ) 

以降、同様に計算