[백준 24479] 알고리즘 수업 - 깊이 우선 탐색 1

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

 

문제 분석

 

입력 받아 그래프를 만들고 DFS로 탐색을 하고, 탐색 순서를 기록하여 출력하는 형식에 문제이다. 

 

이 문제는 DFS만 알고 있다면 딱히 문제 없이 풀 수 있을 것이라고 생각된다. 

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> graph;
vector<bool> visited;
int result[100001];
int cnt = 0;

void DFS(int index);

int main()
{
    int n, m, r, input1, input2;
    cin >> n >> m >> r;

    graph.resize(n + 1);
    visited.resize(n + 1, false);

    while (m--)
    {
        cin >> input1 >> input2;
        graph[input1].push_back(input2);
        graph[input2].push_back(input1);
    }

    for (int i = 1; i < graph.size(); ++i)
        sort(graph[i].begin(), graph[i].end());

    DFS(r);

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

void DFS(int index)
{
    if (visited[index])
        return;

    visited[index] = true;
    ++cnt;
    result[index] = cnt;

    for (int i : graph[index])
        DFS(i);

}