백준 BOJ 11724 - 연결 요소의 개수

www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

간단한 DFS 문제

무방향 그래프를 입력을 통해 만들어주고, 그 뒤에 dfs나 bfs 아무거나 하나 골라서 탐색해준다음

갯수만 세주면 된다.

나는 귀찮은관계로 클래식하게 재귀를 이용한 탐색을 사용했다.

 

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> v[1001];
int visit[1001] = {0};

void dfs(int node){
	if(visit[node] == 1) return;
	else visit[node] = 1;
	
	for(int i=0; i<v[node].size(); i++){
		dfs(v[node][i]);
	}
	return;
}

int main(){
	int n,m;
	int a,b;
	int ans = 0;
	scanf("%d %d", &n, &m);
	for(int i=0; i<m; i++){
		scanf("%d %d", &a, &b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	
	for(int i=1; i<=n; i++){
		if(visit[i] == 0){
			dfs(i);
			ans++;
		}
	}
	printf("%d", ans);
	return 0;
}