백준/24480/DFS/알고리즘 수업 - 깊이 우선 탐색2

백준/24480/DFS/알고리즈 수업 - 깊이 우선 탐색2

문제 해석

깊이 우선 탐색을 하는데 방문 순서를 내림 차순으로하는 문제입니다.

문제 풀이

인접 행렬을 포현한 벡터를 정렬해주고 DFS를 실행시켜주면 되는 문제입니다.

풀이

첫번째 풀이

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int N, M, R;

vector<int>adj[100'001];
int visited[100'001];
int visited_count = 1;

void dfs(int st)
{
	for (int i = adj[st].size()-1;i >= 0;i--)
	{
		if (!visited[adj[st][i]])
		{
			visited[adj[st][i]] = visited_count++;
			dfs(adj[st][i]);
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> M >> R;

	for (int i = 0;i < M;i++)
	{
		int u, v = 0;
		cin >> u >> v;

		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	for (int i = 1;i <= N;i++)
	{
		::sort(adj[i].begin(), adj[i].end());
	}

	visited[R] = visited_count++;

	dfs(R);

	for (int i = 1;i <= N;i++)
	{
		cout << visited[i] << '\n';
	}

	return 0;
}