fork download
  1. # https://a...content-available-to-author-only...r.jp/contests/dp/submissions/20050310
  2.  
  3. # 再帰上限を増やすimport sys
  4. import sys
  5. from collections import deque
  6.  
  7. sys.setrecursionlimit(1000000)
  8.  
  9. N, M = list(map(int, input().split()))
  10.  
  11. # edges[i]: 頂点 i から辺が伸びている頂点たち(隣接リスト)
  12. edges = []
  13. for i in range(N):
  14. edges.append([])
  15.  
  16. # 入次数。始点の判定に使う
  17. indeg = [0] * N
  18.  
  19. # 辺の入力を受け取り、隣接リストを作る
  20. for i in range(M):
  21. x, y = list(map(int, input().split()))
  22. edges[x - 1].append(y - 1)
  23. indeg[y - 1] += 1
  24.  
  25. # トポロジカルソートを実行し、結果を格納するリスト
  26. order = []
  27.  
  28. # 入次数が0の頂点をキューに追加
  29. queue = deque([i for i in range(N) if indeg[i] == 0])
  30.  
  31. while queue:
  32. # キューから頂点を取り出す
  33. u = queue.popleft()
  34. order.append(u)
  35.  
  36. # u から伸びる辺を削除し、入次数が0になった頂点をキューに追加
  37. for v in edges[u]:
  38. indeg[v] -= 1
  39. if indeg[v] == 0:
  40. queue.append(v)
  41.  
  42. # 各頂点から始まる最長経路の長さを格納するリスト
  43. length = [0] * N
  44.  
  45. # トポロジカルソートで得られた順序に沿って最長経路を更新
  46. for u in order:
  47. for v in edges[u]:
  48. length[v] = max(length[v], length[u] + 1)
  49.  
  50. print(max(length))
  51.  
Success #stdin #stdout 0.03s 9704KB
stdin
5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3
stdout
3