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

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

 

문제 설명

정점의 개수(n)과 간선의 개수(m)이 주어졌을 때 다음 m개의 줄에 간선의 양 끝점이 주어진다. 연결된 컴포넌트의 개수를 구하는 문제이다.

 

주요 로직

1. dfs로 푼다
-> 연결된 컴포넌트의 개수를 찾으면 된다.

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

int n,m,a,b,ret;
int visited[1004];
vector<int> arr[1004];

void dfs(int a){
	visited[a] = 1;
	for(auto it : arr[a]){
		if(visited[it]) continue;
		dfs(it);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> n >> m;
	for(int i=0; i<m; i++){
		cin >> a >> b;
		arr[a].push_back(b);
		arr[b].push_back(a);
	}
	
	for(int i=1; i<=n; i++){
		if(visited[i]) continue;
		dfs(i);
		ret++;
	}
	
	cout << ret << "\n";
	
	return 0;
}