[백준 16964] DFS 스페셜 저지

문제

www.acmicpc.net/problem/16964

 

알고리즘

DFS

 

풀이

그래프와 방문 순서가 주어질 때, 올바른지 확인하는 문제입니다.

 

그래프는 2차원 벡터로 표현이 가능합니다. 문제에서 입력을 받는 순서로 그래프를 만들어 방문하는 대신, 방문 순서를 기준으로 그래프를 정렬합니다. 이후 루트 노드에서 DFS를 수행하면 방문 순서가 빠른 노드부터 방문하게 되므로 해당 방문 순서가 올바른 순서인지 파악할 수 있습니다. 이를 위해 $rev$배열을 만들어 방문 순서가 빠른 노드로 그래프를 정렬하도록 했습니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

const int MAXN = 1e5;

int N, seq[MAXN], rev[MAXN], idx;
vector<int> adj[MAXN];

void dfs(int here, int p) {
    if (seq[idx] != here) {
        cout << 0;
        exit(0);
    }
    if (idx == N - 1) {
        cout << 1;
        return;
    }
    ++idx;
    for (auto there : adj[here]) {
        if (there ^ p) {
            dfs(there, here);
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N;
    rep(i, N - 1) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    rep(i, N) {
        int x;
        cin >> x;
        --x;
        seq[i] = x;
        rev[x] = i;
    }
    rep(i, N) {
        sort(adj[i].begin(), adj[i].end(), [](int a, int b) { return rev[a] < rev[b]; });
    }
    dfs(0, -1);
    return 0;
}