[백준] 15805 트리 나라 관광 가이드

dfs순서로 방문한다는 점을 이용해서 답을 찾으면 된다

나는 set충이므로 set을 사용했다..!

1. set에 방문한 정점을 담는다

2. 새로운 정점을 방문했다면 그 이전 정점이 부모다

(부모에서 자식으로 가므로)

3. 이미 방문한 정점이면 건너뛴다

4. set의 크기 == 정점 수

소스코드

#include <iostream>
#include <set>
#include <vector>
using namespace std;
int n;
int arr[200020], ans[200020];
set<int>s;
 
int main() {
    scanf(" %d", &n);
    for (int i = 0; i < n; i++) scanf(" %d", &arr[i]);
 
    ans[arr[0]] = -1;
    s.insert(arr[0]);
    for (int i = 1; i < n; i++) {
        if (s.count(arr[i])) continue;
        ans[arr[i]] = arr[i - 1];
        s.insert(arr[i]);
    }
    printf("%d\n", s.size());
    for (int i = 0; i < s.size(); i++) printf("%d ", ans[i]); puts("");
}