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

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

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

[난이도] Gold4

[유형] DFS

[풀이]

인접리스트를 만들 때 vector 대신 set을 이용하면

방문하지 않은 자식 노드들 중에 입력으로 주어진 다음에 방문해야 하는 노드가

있는지를 쉽게 파악할 수 있습니다.

노드가 존재한다면 그 노드를 set에서 제거해주고 다음 노드로 방문해주면 됩니다.

#include #include using namespace std; int idx,N,a[100001]; set 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

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

from http://leesh111112.tistory.com/355 by ccl(A) rewrite - 2021-12-18 22:01:09