정수 막대 목록이 있다고 가정합니다. 여기서 목록의 각 요소는 두 끝이 있는 막대를 나타내며 이 값은 1에서 6 사이입니다. 이들은 각 끝을 나타냅니다. 끝이 같은 막대가 있으면 두 막대기를 함께 연결할 수 있습니다. 결과 스틱의 끝은 남은 끝이 되며 길이가 늘어납니다. 가능한 가장 긴 막대기의 길이를 찾아야 합니다.
따라서 입력이 스틱 =[ [2, 3], [2, 4], [3, 5], [6, 6] ]과 같으면 출력은 [2, 3]을 연결할 수 있으므로 3이 됩니다. ] 및 [2, 4]는 [3, 4]를 가져오고 [3, 5]와 연결하여 [4, 5]를 얻을 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다.
-
dfs() 함수를 정의합니다. 이것은 node, edge_idx 및 방문한 세트를 취합니다.
-
edge_idx가 null이 아니면
-
edge_idx를 방문하면
-
0 반환
-
-
edge_idx를 방문한 것으로 표시
-
해상도 :=0
-
g[노드]의 각 e_idx에 대해 수행
-
n_node :=sticks[e_idx, 0]일 때 sticks[e_idx, 1]이 노드와 같으면 sticks[e_idx, 1]
-
res :=최대 res 및 1 + dfs(n_node, e_idx, 방문)
-
-
edge_idx가 0이 아니면
-
방문에서 edge_idx 삭제
-
-
반환 해상도
-
-
기본 방법에서 다음을 수행합니다.
-
스틱 :=스틱의 모든 s에 대한 목록(s[0], s[1])
-
정점 :=새로운 세트
-
g :=빈 지도
-
막대의 각 인덱스 i와 가장자리에 대해
-
g[edge[0]]에 i 삽입
-
g[edge[1]]에 i 삽입
-
edge[0]과 edge[1]을 꼭짓점에 삽입
-
-
해상도 :=0
-
정점의 각 v에 대해 수행
-
res :=res 및 dfs(v, null 및 빈 집합)의 최대값
-
-
반환 해상도 - 1
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
예시
from collections import defaultdict class Solution: def solve(self, sticks): def dfs(node, edge_idx, visited): if edge_idx is not None: if edge_idx in visited: return 0 visited.add(edge_idx) res = 0 for e_idx in g[node]: n_node = sticks[e_idx][0] if sticks[e_idx][1] == node else sticks[e_idx][1] res = max(res, 1 + dfs(n_node, e_idx, visited)) if edge_idx: visited.remove(edge_idx) return res sticks = [(s[0], s[1]) for s in sticks] vertices = set() g = defaultdict(set) for i, edge in enumerate(sticks): g[edge[0]].add(i) g[edge[1]].add(i) vertices.add(edge[0]) vertices.add(edge[1]) res = 0 for v in vertices: res = max(res, dfs(v, None, set())) return res - 1 ob = Solution() sticks = [ [2, 3], [2, 4], [3, 5], [6, 6] ] print(ob.solve(sticks))
입력
sticks = [ [2, 3], [2, 4], [3, 5], [6, 6] ]
출력
3