그래프가 인접 목록으로 있다고 가정합니다. 이 그래프는 실제로 분리된 트리의 집합입니다. 하나의 나무가 되도록 숲에 특정 수의 가장자리를 추가해야 합니다. 두 노드 사이의 가장 긴 경로의 가능한 최소 거리를 반환해야 합니다. 따라서 입력이 다음과 같으면
그러면 출력은 4가 됩니다.
모서리 0 −> 5를 추가할 수 있습니다. 그러면 가장 긴 경로는 3 −> 1 −> 0 −> 5 −> 7 또는 4 −> 1 −> 0 −> 5 −> 7 중 하나가 될 수 있습니다. 또한 방향이 반전 된 이러한 경로. 그래서 우리는 거리 4를 반환합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
본 :=새로운 세트
-
dic :=그래프
-
함수 treeDepth()를 정의합니다. 노드가 필요합니다.
-
ret :=0
-
dfs1() 함수를 정의합니다. 이것은 노드, 부모를 취합니다.
-
본 세트에 노드 추가
-
best2 :=빈 최소 힙 구조
-
dic[node]의 각 nxt에 대해 수행
-
nxt가 부모와 같지 않으면
-
push(dfs1(nxt, node) + 1)을 best2로
-
-
len(best2)> 2이면
-
힙에서 팝(best2)
-
-
best2가 비어 있으면
-
0 반환
-
-
ret :=ret의 최대값, best2의 모든 요소의 합
-
best2의 최대값을 반환합니다.
-
-
dfs1(노드, 널)
-
리턴 렛
-
-
-
주요 방법에서 다음을 수행하십시오 -
-
ret :=0, opt :=새 목록, 노래 :=0
-
범위 0에서 그래프 크기까지의 노드에 대해
-
노드가 보이는 경우
-
다음 반복으로 이동
-
-
res :=treeDepth(노드)
-
노래 :=노래의 최대값, res
-
opt의 끝에 (res / 2)의 천장을 삽입하십시오.
-
-
opt <=1인 경우
-
반환 노래
-
-
mx :=opt의 최대값
-
범위 0에서 opt 크기까지의 i에 대해
-
opt[i]가 mx와 같으면
-
옵트[i] :=옵트[i] − 1
-
루프에서 나오다
-
-
-
범위 0에서 opt 크기까지의 i에 대해
-
선택[i] :=선택[i] + 1
-
-
high2 :=opt에서 가장 큰 2개의 요소
-
sum(high2)의 최대값을 반환하고 노래
-
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
import heapq, math class Solution: def solve(self, graph): seen = set() dic = graph def treeDepth(node): self.ret = 0 def dfs1(node, parent): seen.add(node) best2 = [] for nxt in dic[node]: if nxt != parent: heapq.heappush(best2, dfs1(nxt, node) + 1) if len(best2) > 2: heapq.heappop(best2) if not best2: return 0 self.ret = max(self.ret, sum(best2)) return max(best2) dfs1(node, None) return self.ret ret = 0 opt = [] sing = 0 for node in range(len(graph)): if node in seen: continue res = treeDepth(node) sing = max(sing, res) opt.append(int(math.ceil(res / 2))) if len(opt) <= 1: return sing mx = max(opt) for i in range(len(opt)): if opt[i] == mx: opt[i] −= 1 break for i in range(len(opt)): opt[i] += 1 high2 = heapq.nlargest(2, opt) return max(sum(high2), sing) ob = Solution() graph = [ [1, 2], [0,3,4], [0], [1], [1], [6,7], [5], [5] ] print(ob.solve(graph))
입력
graph = [ [1, 2], [0,3,4], [0], [1], [1], [6,7], [5], [5] ]
출력
4