[C/C++ 백준 11724번] 연결 요소의 개수 (Silver 2)

www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

탐색의 방법에 상관없이 모두 탐색을 하기만 하면 상관없다.

모든 정점에 대해 for문을 돌리면서, 탐색이 되지 않았을 경우에만 답에 ++을 해주면 쉽게 풀 수 있다.

 

#include <cstdio>
#include <vector>
using namespace std;
void dfs(int start, vector <int> graph[], bool visited[]){
	if(visited[start])
		return ;
	visited[start] = true;
	for(int i=0; i<graph[start].size(); i++){
		if(!visited[graph[start][i]]){
			dfs(graph[start][i], graph, visited);
		}
	}
}
int main(void){
	int N, M, A, B, cnt=0;
	scanf("%d %d", &N, &M);
	vector <int> graph[N+1];
	bool visited[N+1];
	for(int i=1; i<N+1; i++){
		visited[i] = false;
	}
	for(int i=0; i<M; i++){
		scanf("%d %d", &A, &B);
		graph[A].push_back(B);
		graph[B].push_back(A);
	}
	for(int i=1; i<=N; i++){
		if(!visited[i]){
			cnt++;
			dfs(i, graph, visited);
		}
	}
	printf("%d", cnt);
}