16940번 BFS 스페셜 저지

이미 짜인 그래프에서, 입력이 들어올 때 그 순서대로 BFS를 했을 때 통과되는지를 확인하는 문제이다. 입력이 여러개가 가능한 이유는, BFS가 하나의 점을 queue에서 빼낼 때, 그 점에서 연결된 점들 중, 어떤 순서대로 빼든지 상관이 없기 때문이다.
1. check 배열 - 이미 꺼낸 점인지 확인
2. parent 배열 - queue에 push할때에 어떤 점과 연결되어 있는지 확인
3. order 배열 - 입력이 들어온 배열

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int ch[100001];
//int parent[100001];
int order[100001];
vector<int> graph[100001];
int main() {
	ios_base::sync_with_stdio(false);
	//freopen("in1.txt", "rt", stdin);
	int n, i, j, a, b;
	cin >> n;
	
	for (i = 1; i < n; i++) {
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	for (i = 0; i < n; i++) {
		cin >> order[i];
	}
	int m = 0;
	queue<int> Q;
	Q.push(1);
	ch[1] = 1;
	for (int i = 0; i < n; i++) {
		//cout << "why?" << '\n';
		if (Q.empty()) {
			cout << "0" << '\n';
			return 0;
		}
		int tmp = Q.front();
		Q.pop();
		if (tmp != order[i]) {
			cout << "0" << '\n';
			return 0;
		}
		int cnt = 0;
		for (int k = 0; k < graph[tmp].size(); k++) {
			if (ch[graph[tmp][k]] == 0) {
				ch[graph[tmp][k]] = 1;
				//parent[graph[tmp][k]] = tmp;
				cnt++;
			}
		}
		for (j = 1; j <= cnt; j++) {
			Q.push(order[m + j]); // 2 , 3
			ch[order[m + j]] = 1;
		}
		m += cnt;
	}
	cout << "1" << '\n';
	return 0;
}