백준 11724 : 연결 요소

1379 단어 DFScppDFS

★★☆☆☆
연결요소가 무엇인지 몰라서 개념을 공부해야했지만,
그래프에서는 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 변수를 이용해 연결 요소값을 증가시켜준다.

좋은 웹페이지 즐겨찾기