백준 11724 : 연결 요소

★★☆☆☆
연결요소가 무엇인지 몰라서 개념을 공부해야했지만,
그래프에서는 dfs와 bfs를 사용하면 된다고 생각하니 구현은 금방 되었다.

개념

연결 요소(Connected Component) 는 그래프 내에서의 묶음? 과 같은 개념이다.
모든 그래프가 이어져있는것만은 아니기때문에 이러한 연결요소가 발생한다.

나의 풀이

#include <iostream>
#define MAX 1001
using namespace std;

int n, m;
bool graph[MAX][MAX];
bool visited[MAX];

void dfs(int start) {
	visited[start] = true;
	//cout << start << " ";

	for (int i = 0; i <= n; i++) {
		if (!visited[i] && graph[start][i]) {
			dfs(i);
		}
	}
	return;
}


int main() {
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;

		graph[x][y] = true;
		graph[y][x] = true;
	}
	
	int count=0;
	for (int i = 1; i <= n; i++) {
		if (visited[i]) continue; //이미 연결요소의 일부로 카운트됨
		else {
			//cout << "시작점 " << i << " case -------------------\n";
			dfs(i);
			//cout << "\n";
			count++;
		}
	}
	cout << count << "\n";

}

지난번 dfs 구현을 이용해서, 먼저 입력값들로 그래프를 만들고,
시작점을 1~n까지 변경하면서 dfs를 진행했다.
이때, 하나의 연결요소 안에 속한 정점들은 한꺼번에 visited 처리가 되므로,
방문되지 않은 정점들을 중심으로 dfs를 다시 실행해준다.
실행 횟수마다 count 변수를 이용해 연결 요소값을 증가시켜준다.