문제

입력

입출력 예시

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<vector<int>> islands;
vector<int> visit;
int N, M;

void bfs(int start) {
	visit[start] = 1;
	queue<int> q;
	q.push(start);
	
	while(!q.empty()) {
		int next = q.front();
		q.pop();
		for(int i = 1; i <= N; i++) {
			if(!visit[i] && islands[next][i]) {
				visit[i] = 1;
				q.push(i);
			}
		}
	}
}

int bfsAll() {
	int cnt = 0;
	visit = vector<int>(N + 1, 0);
	for(int i = 1; i <= N; i++) {
		if(!visit[i]) {
			bfs(i);
			++cnt;
		}
	}
	return cnt;
}

int main() {
	cin >> N >> M;
	vector<vector<int>> temp(N + 1, vector<int>(N + 1, 0));
	islands = vector<vector<int>>(N + 1, vector<int>(N + 1, 0));
	
	for(int i = 0; i < M; i++ ){
		int a, b;
		cin >> a >> b;
		temp[a][b] = 1;
	}
	
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++) {
			if(temp[i][j] && temp[j][i]) {
				islands[i][j] = 1;
				islands[j][i] = 1;
			}
		}
	}
	cout << bfsAll();
	return 0;
	
}

N이 최대 2000개로 적기 때문에 for문을 두 번 돌려 양방향인지 아닌지 확인해도 된다