[AtCoder][競プロ][DP][Educational DP Contest]G-Longest Path

AtCoder

Photo by Corinna Widmer on Pexels.com

2022.05.28

Table of Contents

Educational DP Contest

AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

問題

G - Longest Path

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

方針

最初にリストに各点から到達しうる点を収納する。DPとしては、\(dp(i)\)を「頂点\(i\)」から開始するパスで最も長いもの」とする。すると、\(i\)から到達できる点を\(v_i\)とすると、\(dp(i) = max(dp(v_i))\)となる。この式を見ると再帰 recursionを用いることができそうだと考える。Python3のrecursionは上限があるので、

import sys
sys.setrecursionlimit(10**7)

で上限を外しておく。

解答

#atcoder template
def main():
    import sys
    input = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    sys.setrecursionlimit(10**7)
    n, m = map(int, input().split())
    z = [[] for _ in range(n)]
    visited = [0] * n
    memo = [0] * n
    def dp(v):
        if visited[v]:
            return memo[v]
        else:
            res = 0
            for u in z[v]:
                res = max(res, dp(u) + 1)
            memo[v] = res
            visited[v] = 1
            return res
    for i in range(m):
        x, y = map(int, input().split())
        z[x-1].append(y-1)
    for i in range(n):
        dp(i)
    print(max(memo))
    
    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()