구름톤 4주차 후기 (1)

 

문제에서 요구하는 연합의 개수가 곧 우리가 평소 풀던 그래프 문제의 다리 역할을 한다.

하나만 연결되어있는 다리는 연합끼리 이어주기는 하지만 그 이상, 그이하도 아니다.

애초에 연합이어야 다른 연합이랑 이어질 수 있기 때문에, 연합인지 아닌지 판별해서 그래프 탐색을 하는게 중요하다.

 

따라서 처음엔 연합판별을 한 후 새로운 그래프를 만들어서 탐색하려다가,

그냥 평범한 BFS 에서 한번더 반대편 다리도 체크해서 queue에 넣는 작업 하나와, 2001 짜리 visited 배열로 섬 방문 여부를 확인할 수 있도록 했다.

 

#include <iostream>
#include <queue>
using namespace std;
long long N,M;

int graph[2001][2001] ={};
int visited[2001] = {};


/*
 	1 2 3 4 
1   1   1
2     1 1
3		    1
4 1

 	1 2 3 4 
1 1     1
2   1   1
3		  1 
4 1     1
*/
void BFS(int a){
	queue<int> Q;

	Q.push(a);
	visited[a] = 1;
	while(!Q.empty()){
		int cur = Q.front();
		Q.pop();
		
		for(int i = 1; i <= N; i++){
			if(graph[cur][i] == 1 && graph[i][cur] == 1 && visited[i] == 0){
				Q.push(i);
				visited[i] = 1;
			}
		}
	}	
}

int main() {
	
	cin >> N >> M;
	
	//서로 연결되었다면 연합(양방향일 때.). 같은 연합을 다리라고 친다음, 연합을 BFS로 탐색
	int a, b;
	for(int i = 0; i < M; i++){
		cin >> a >> b;
		graph[a][b]++;
	}
	
	int count = 0;
	for(int i = 1; i <= N; i++){
		if(visited[i] == 0){
			BFS(i);
			count++;
		}
	}	
	
	cout << count;	
	return 0;
}