알고리즘 수업 - 깊이 우선 탐색 2 (feat. 백준, 24480번)

알고리즘 수업 - 깊이 우선 탐색 2
https://www.acmicpc.net/problem/24480

24480번: 알고리즘 수업 - 깊이 우선 탐색 2

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <set>
#include <map>
using namespace std;
struct Cmp {
	bool operator()(const int& v1, const int& v2) const {
		return v1 > v2;
	}
};
int N, M, R, cnt, ans[100001];
bool visit[100001];
map<int, set<int, Cmp>, Cmp> arr;
void dfs(int r) {
	ans[r] = ++cnt;
	visit[r] = true;
	for (auto iter = arr[r].begin(); iter != arr[r].end(); ++iter)
		if (!visit[*iter])
			dfs(*iter);
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> N >> M >> R;
	cnt = 0;
	memset(ans, 0, sizeof(ans[0]) * (N + 1));
	memset(visit, false, N + 1);
	for (register int i = 0, u, v; i < M; ++i)
		cin >> u >> v, arr[u].insert(v), arr[v].insert(u);
	dfs(R);
	for (register int i = 1; i <= N; ++i)
		cout << ans[i] << "\n";
	return 0;
}
// *&)*@*

1. 이전 '알고리즘 수업 - 깊이 우선 탐색 1' 과 동일하지만 내림차순부터 시작한다는 것만 다를 뿐입니다.
2. 따라서 아래 문제를 선행하시길 권장합니다.

알고리즘 수업 - 깊이 우선 탐색 1 (feat. 백준, 24479번)