인접 목록으로 표현되는 하나의 방향성 비순환 그래프가 있다고 가정합니다. 노드 반복 없이 그래프에서 가장 긴 경로를 찾아야 합니다.
따라서 입력이 다음과 같으면
경로는 0 -> 1 -> 3 -> 4 -> 2이고 길이는 4이므로 출력은 4가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- ans :=0
- n :=그래프의 노드 수
- table :=크기가 n인 목록과 -1로 채우기
- dfs() 함수를 정의합니다. 이것은 당신을 걸릴 것입니다
- 테이블[u]가 -1이 아니면
- 반환 테이블[u]
- p_len :=0
- 그래프[u]의 각 vectex v에 대해 다음을 수행합니다.
- p_len :=p_len의 최대값 및 (1 + dfs(v))
- 테이블[u] :=p_len
- p_len 반환
- 메인 방법에서 다음을 수행하십시오 -
- 0에서 n 사이의 i에 대해
- ans :=최대 ans, dfs(i)
- 반환
예제(파이썬)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
class Solution: def solve(self, graph): ans = 0 n = len(graph) table = [-1] * n def dfs(u): if table[u] != -1: return table[u] p_len = 0 for v in graph[u]: p_len = max(p_len, 1 + dfs(v)) table[u] = p_len return p_len for i in range(n): ans = max(ans, dfs(i)) return ans ob = Solution() graph = [ [1, 2], [3, 4], [], [4], [2], ] print(ob.solve(graph))
입력
graph = [[1, 2],[3, 4],[],[4],[2]]
출력
4