백준 11724. 연결 요소의 개수

백준 11724. 연결 요소의 개수

1. 문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

연결 요소 (위키피디아)

2. 입력

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

3. 출력

첫째 줄에 연결 요소의 개수를 출력한다.

4. 풀이

• DFS로 풀었다.
• 기존 DFS 문제랑 유사했고 특별한 건 없었다.
• DFS로 노드를 방문한다.
• 방문한 노드를 방문 표시 해주고 방문 안 된 노드만 main에서 DFS한다.
• DFS한 횟수 = 연결 요소의 개수

5. 첫 코드에서 수정한 점

• 특별한 건 없었고 dfs 함수에서 visited 배열을 true로 바꾸는(방문표시하는) 구문을 빼먹었다.
• 추가하니까 통과했다.

6. 소스

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<int> graph[1001];
bool visited[1001];

void dfs(int x){
	visited[x] = true;
    for(int i=0; i<graph[x].size(); i++){
		int y = graph[x][i];
		if(!visited[y]) dfs(y);
	}
}

int main(){
	int answer = 0;
	cin>>n>>m;
	for(int i=0; i<m; i++){
		int from, to;
		cin>>from>>to;
		graph[from].push_back(to);
		graph[to].push_back(from);
	}
	
	for(int i=1; i<=n; i++){
		if(!visited[i]){
			dfs(i);
			answer++;
		}
	}
	
	cout<<answer<<endl;
}