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

홍시홍 2020. 1. 13. 01:14

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

11724번: 연결 요소의 개수

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

www.acmicpc.net

요구사항

연결 요소의 개수 구하기

풀이

이어져있는 덩어리가 몇개인가를 dfs로 구하였다

#include <iostream>

using namespace std;
int n, m;
int map[1001][1001];
int visit[1001];
void dfs(int start, int next) {
	for (int i = 1; i <= n; i++) {
		if (map[next][i] == 1 && visit[i] == 0) {
			visit[i] = 1;
			dfs(start, i);
		}
	}
}
int main() {
	int ans = 0;
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		map[x][y] = map[y][x] = 1;
	}
	for (int i = 1; i <= n; i++) {
		if (visit[i] == 0) {
			ans++;
			dfs(i, i);
		}
	}
	cout << ans << endl;
}