BFS 스페셜 저지

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

16940번: BFS 스페셜 저지

인접 리스트에 간선을 넣은 순서에 따라서

BFS의 순서가 달라진다!

 

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
vector<int> a[100000];
int parent[100000];
int ans[100000];
bool check[100000];
 
 
int main()
{
    int n;
    cin >> n;
 
    for (int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        u -= 1; v -= 1;
        a[u].push_back(v);
        a[v].push_back(u);
    }
 
 
    for (int i = 0; i < n; i++)
    {
        cin >> ans[i];
        ans[i] -= 1;
    }
    
    queue<int> q;
    q.push(0);
    check[0] = true;
 
    int m = 1;
 
    for (int i = 0; i < n; i++)
    {
        //아직 BFS가 진행중인데 큐가 비었다
        if (q.empty())
        {
            cout << 0 << '\n';
            return 0;
        }
 
        int x = q.front(); 
        q.pop();
 
        //순서가 올바르지 않음
        if (x != ans[i])
        {
            cout << 0 << '\n';
            return 0;
        }
 
        int cnt = 0;
        for (int y : a[x])
        {
            if (check[y] == false)
            {
                parent[y] = x;
                cnt += 1;  // 자식 개수
            }
        }
 
        for (int j = 0; j < cnt; j++)
        {
            if (m + j >= n || parent[ans[m + j]] != x)
            {
                cout << 0 << '\n';
                return 0;
            }
            q.push(ans[m + j]);
            check[ans[m + j]] = true;
        }
 
        m += cnt;
    }
 
    cout << 1 << '\n';
    return 0;
}