[백준] 11724번: 연결 요소의 개수 [C++]

 

알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

 

 

【 풀이 】

 

서로 연결되어 있는 정점의 그룹이 몇 개인지를 구하는 문제이다.

정점이 서로 연결되어 있는지만 확인하면 되므로, 비교적 구현하기 쉬운 DFS 로 문제를 해결했다.

 

DFS 함수를 호출할 때 연결되어 있는 곳은 이미 다 방문처리가 되므로,

반복문으로 모든 정점을 순회하게 한 다음, 방문하지 않은 곳을 방문하고자 한다면 정답의 개수를 하나씩 늘리면 된다. 

 

 

 

【 코드 】

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

vector<bool>visited(1001,false);
vector<int>graph[1001];

void CreateGraph(int ver) {
	for (int i = 0; i < ver; i++) {
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
}

void dfs(int here) {
	visited[here] = true;
	for (int i = 0; i < graph[here].size(); i++) {
		int there = graph[here][i];
		if (!visited[there])
			dfs(there);
	}
}

int main() {
	int cnt = 0;
	int n, m;
	cin >> n >> m;

	CreateGraph(m);

	for (int i = 1; i <= n; i++) {
		if (!visited[i])
			cnt++;
		dfs(i);
	}

	cout << cnt;

	return 0;
}