[C++/24391] 귀찮은 해강이

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

BFS를 이용해서 각 각의실마다 그룹을 나눠서 등록해두면 됩니다. 그 이후, 강의실을 돌아다니면서 몇번 바깥을 나가게 되는지를 알아볼 수 있습니다.

아래는 정답 코드입니다.

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

#define MAX 100005
using namespace std;

vector<int> code,adj[MAX];
int answer = 0,n,m,lecture[MAX],visited[MAX];

void init(){
	
	cin >> n >> m;
	
	int from,to;
	
	for(int i = 0; i < m; i++){
		cin >> from >> to;
		adj[from].push_back(to);
		adj[to].push_back(from);
	}
	
	int number;
	for(int i = 0; i < n; i++){
		cin >> number;
		code.push_back(number);
	}

}

void move(int start, int idx) {
	
	queue<int> q;
	q.push(start);
	lecture[start] = idx;
	
	while(!q.empty()){
		
		int from = q.front();
		q.pop();
		
		for(int i = 0; i < adj[from].size(); i++){
			int to = adj[from][i];
			
			if(!lecture[to]){
				lecture[to] = idx;
				q.push(to);
			}
		}
		
	}
	
}

void bfs() {
	
	memset(lecture, 0, sizeof(lecture));

	for(int i = 0; i < n; i++){
		if(lecture[code[i]]) continue;
		move(code[i], i+1);
	}
	
}

void solve() {
	
	int current = lecture[code[0]];
	
	for(int i = 1; i < n; i++){
		if(current != lecture[code[i]]){
			answer++;
			current = lecture[code[i]];
		} 
	}
	
	cout << answer;
}

int main(){
	
	init();
	bfs();
	solve();
	
	return 0;
}