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

11724번: 연결 요소의 개수 (acmicpc.net)

11724번: 연결 요소의 개수

---

난이도 : 실버2

 

문제 설명 :

연결 요소란, 무방향 그래프에서 적어도 한 개 이상의 경로로 연결된 정점들로 구성된 종속 그래프를 이야기합니다.

예를 들어, 아래와 같은 그림이 있을 때, 연결 요소의 개수는 2개입니다. (각각의 떨어져 있는 그래프가 2개!)

 

 

출처 : https://velog.io/@polynomeer/%EC%97%B0%EA%B2%B0-%EC%9A%94%EC%86%8CConnected-Component

 

풀이 과정 : 

DFS나 BFS로 풀 수있는 문제입니다. 

이 문제를 풀기 전에 dfs와 bfs문제를 풀어보고 오시면 문제가 엄청 쉬워집니다!!

[C++] 1260 DFS와 BFS (tistory.com)

[C++] 1260 DFS와 BFS

저는 DFS로 풀었고, 정점의 개수만큼 1부터 DFS를 돌린 후, 방문하지 않은 노드가 있으면

그 노드로 이루어진 그래프는 또다른 연결요소가 되므로 반복문을 돌려주며 dfs한 횟수를 cnt에 더해줍니다.

 

코드 :

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

int n, m;
vector<int> adj[1002];
bool visited[1002];
void dfs(int now) {
	visited[now] = 1;
	for (int i = 0; i < adj[now].size(); i++){
		int next = adj[now][i];
		if (!visited[next]) dfs(next);
	}
}


int main() {

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	for (int j = 1; j <= n; j++) {
		sort(adj[j].begin(), adj[j].end());
	}
	
	int cnt = 0;
	for (int k = 1; k <= n; k++) {
		if (visited[k]) continue;
		dfs(k);
		cnt++;
	}
	cout << cnt;
}