(백준 11724번 연결 요소의 개수 C++) 라이님 블로그 대회 알고리즘 따라잡기 8) DFS 1

그 유명하다는 DFS! 자세한 설명은 라이님의 블로그를 참고해서 공부해보았다.

 

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220785731077&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

깊이 우선 탐색(Depth-First Search) (수정 2019-08-18)

 

기본 템플릿은 라이님 블로그를 보면서 익혔다. 

stack으로도 짤 수 있는데, 보다보니 라이님 알고리즘이 직관적이라서 이 템플릿으로 적응할 것 같다ㅎㅎ

 

백준 11724번

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

11724번: 연결 요소의 개수

// 11724번 연결 요소의 개수
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

class Graph {
public:
	int N; 
	vector<vector<int>> v;
	vector<int> visited;

	Graph() :N(0) {}
	Graph(int N) : N(N) {
		v.resize(N);
		visited.resize(N, false);
	}

	void addEdge(int u, int w) {
		v[u].push_back(w);
		v[w].push_back(u);
	}
	void dfs() {
		dfs(0);
	}

	int dfs_component() {
		int comp = 0;
		//fill(visited.begin(), visited.end(), false);
		for (int i = 0; i < N; i++) {
			if (!visited[i]) {
				dfs(i);
				comp++;
			}
		}
		return comp;
	}
private:
	void dfs(int curr) {
		visited[curr] = true;
		for (int next : v[curr]) {
			if (!visited[next]) dfs(next);
		}
	}
};
int main() {
	int N, M;
	scanf("%d %d", &N, &M);
	Graph g(N);
	
	for (int i = 0; i < M; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		//★ vertex는 1이 아닌 0부터 시작해야함
		g.addEdge(u-1, v-1);
	}
	printf("%d", g.dfs_component());
	return 0;
}