노드의 부모 목록에서 트리를 만드는 방법은 무엇입니까?

각 노드의 부모를 알고 있습니다. 그것은 unordered_map 플랫에 저장됩니다. 각 노드는 숫자로, 0은 루트를 의미합니다. 어떻게 그 정보로부터 나무를 효율적으로 만들 수 있습니까?노드의 부모 목록에서 트리를 만드는 방법은 무엇입니까?

struct node { 
    int id; 
    unordered_set<node> children; 
};

일부 노드가 루트에 전혀 연결되어 있지 않을 수도 있습니다. 분리 된 체인은 무시할 수 있으며 결과 트리의 일부일 필요는 없습니다.

필요한 경우 자세한 내용을 문의하십시오.

2014-05-24 danijar

노드 포인터의 배열을 만듭니다.

그런 다음 배열의 주어진 색인에있는 노드를 부모 배열의 색인에있는 노드의 children에 추가하여지도를 살펴보십시오.

그러면 색인 0의 노드가 트리의 루트가됩니다.

2014-05-24 11:24:08 Dukeling

"그러면 인덱스 0에있는 노드가 트리의 루트가됩니다." 왜 그랬을까요? 물론 부모가없는 노드 (또는 자신이 부모가되는 노드)가 루트입니다. –

포인터를 사용하는 것이 좋습니다. 루트는 이미 ID 0으로 주어집니다. – danijar

@ G.Bach 글쎄, 질문문에서 '0'이 루트 인 것처럼 보일 것입니다. (분리 된 체인이 있으므로 단순히 부모가없는 체인을 찾으면 작동하지 않습니다). – Dukeling

답변