가장자리에서 나무를 만들다

Question

나는 가장자리가 있고 그것으로 나무를 만들고 싶다.

문제는 가장자리가 특정 순서 인 경우에만 트리 구조를 구성 할 수 있다는 것입니다. 주문 예 :

(vertex, parent_vertex) 

good:    bad: 
(0, ) <-top  (3, 2) 
(1, 0)    (1, 0) 
(2, 1)    (3, 2) 
(3, 2)    (0, ) <-top 

은 그때 내가 노드를 구성하고 삽입, 가장자리를 던져 그것을 만든 트리의 부모 찾기 위해 노력하고 현재의 정점을 위해 반복.

result tree: 

0 - 1 - 2 - 3 

새롭게 추가 된 버텍스에는 항상 트리에 부모가 있어야합니다. 질문은 입력 가장자리를 정렬하는 방법입니다. 음성은 위상 적 정렬에 대해 알려주지 만 꼭지점을 나타냅니다. 그것을 바로 정렬 할 수 있습니까?

Answer 1

@mirt 내 접근 방식에 대한 최적화를 지적 해 주셔서 감사합니다. (그 루트를 대표하는 사건/또는 아무것도 널을)

복용 루트를 추가, H : 내가

처음에 트리가있는 요소를 저장하는 해시 맵을 구축 심판

을 위해 너 한테 아래를 넣어 것입니다 쌍 (_child, _parent)

1. 전체 목록을 반복합니다. 목록에 있습니다. (각 쌍은 요소입니다)
2. 각 쌍에 대해 해시지도 H에 _child 및 _parent가 있는지 확인하십시오. 찾지 못하면 누락 된 항목의 트리 노드를 만들어 H에 추가하고 연결합니다 부모 자녀 관계.
3. 반복이 끝나면 트리가 남아있게됩니다.

복잡도는 O (n)입니다.