임의의 트리 T가 주어졌다고 했을때, 그 트리의 노드를 아무거나 n개 뽑아서 N_1, N_2, ..., N_n라고하고
한 번에 어떤 노드가 어떤 노드의 자식인지만 알 수 있다고 할 때,
다음을 만족하는 N={N_1, N_2, ..., N_k}의 부분집합 N'를 구하고 싶음
'임의의 N의 원소 x에 대하여 N'은 x의 조상노드 오직 한 개를 원소로 갖거나 그렇지 않으면, x를 원소로 갖는다.'
N'을 구하는 O((n-1)!)보다 빠른 알고리즘이 존재함?
그러니까 주어진 트리 T의 노드들의 부분집합 N을 N의 부분집합 N'로 보내는 함수 getFounders의 시간 복잡도가 궁금한 거지? 여기서 N' = getFounders(N)일 필요충분조건은 임의의 N의 원소 x에 대하여 x의 조상 노드 중 더 이상 부모가 없거나 N의 원소가 아닌 노드들 그리고 그런 노드들만 N'에 속한다는 게 getFounders의 스펙인데, 쓸 수 있는 함수는 isChildrenOf : N x N to bool인 거고?
만약 저게 문제의 올바른 진술이라면, 트리의 노드들을 전부 나열(enumerate)할 수 있는지부터 궁금해지네.