알고리즘 풀이/백준(Boj)
백준(BOJ) 16964번 DFS 스페셜
100win10
2020. 1. 11. 13:49
문제 : https://www.acmicpc.net/problem/16964
16964번: DFS 스페셜 저지
첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루어져 있으며, 1부터 N까지 자연수가 한 번씩 등장한다.
www.acmicpc.net
풀이 :
order배열을 통해 각 정점에 순서를 구해준다.
각각의 a안에 배열들을 order 순서에 맞게 정렬한다.
이후 바뀐 a로 dfs 방문을 실제로 해보고 picked배열에 저장한다.
picked와 cand가 같지 않으면 0을 같다면 1을 출력한다.
ex)
두번째 예제에서는 a[0]은 1 2 였지만 a[0]은 2 1로 바뀌게 된다.
코드 ( C++ )
