티스토리 뷰
dfs순서로 방문한다는 점을 이용해서 답을 찾으면 된다
나는 set충이므로 set을 사용했다..!
1. set에 방문한 정점을 담는다
2. 새로운 정점을 방문했다면 그 이전 정점이 부모다
(부모에서 자식으로 가므로)
3. 이미 방문한 정점이면 건너뛴다
4. set의 크기 == 정점 수
소스코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | #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(""); } | cs |
'알고리즘 > BOJ' 카테고리의 다른 글
[백준] 15587 Cow at Large (Gold) (0) | 2018.06.01 |
---|---|
[백준] 7578 공장 (0) | 2018.05.30 |
[백준] 15772 Segmentation (0) | 2018.05.29 |
[백준] 15803 PLAYERJINAH’S BOTTLEGROUNDS (0) | 2018.05.29 |
[백준] 15783 세진 바이러스 (0) | 2018.05.28 |
댓글