[BOJ/백준][Gold4] 16964 : DFS 스페셜 저지 (C++)

https://www.acmicpc.net/problem/16964

16964번: DFS 스페셜 저지

 

 

[난이도] Gold4
[유형] DFS

[풀이]
인접리스트를 만들 때 vector 대신 set을 이용하면
방문하지 않은 자식 노드들 중에 입력으로 주어진 다음에 방문해야 하는 노드가
있는지를 쉽게 파악할 수 있습니다.
노드가 존재한다면 그 노드를 set에서 제거해주고 다음 노드로 방문해주면 됩니다.

 

#include <cstdio>
#include <set>
using namespace std;
int idx,N,a[100001];
set<int> adj[100001];
int dfs(int prev,int n){
    idx++;
    if(adj[n].find(prev) != adj[n].end()) adj[n].erase(prev);
    while(!adj[n].empty()){
        int v = a[idx];
        if(adj[n].find(v) == adj[n].end()) return 0;
        adj[n].erase(v);
        bool ret = dfs(n,v);
        if(!ret) return 0;
    }
    return 1;
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N-1;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u].insert(v);
        adj[v].insert(u);
    }
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    printf("%d",dfs(0,1));
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/16964.cpp