알고리즘 수업 - 깊이 우선 탐색 2 (DFS)

* DFS -> 재귀 , stack 으로 푼다.

* sort의 헤더는 algorithm 이다. compare 함수로 내림차순 오름차순 구분할 수 있다. a > b 면 왼쪽이 오른쪽보다 크면 true로, 내림차순이고, return a < b; 면 오름차순이다. 

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

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

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

using namespace std;

#define MAX 100001

int visited[MAX] = {0,};
int result[MAX];
vector<int> graph[MAX];
int cnt = 0;

bool compare(int a, int b) {
    return a > b;
}

void dfs(int x) {
    if(visited[x] == 1) return ;

    visited[x] = 1;
    cnt++;
    result[x] = cnt;
    for(int i = 0; i < graph[x].size(); i++) {
        //printf("graph[%d][%d] : %d\n", x,i, graph[x][i])
        dfs(graph[x][i]);
    }
}


int main() {
    int N, M, R;
    scanf("%d %d %d", &N, &M, &R);
    for(int i = 1; i <= M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(int i = 1; i <= N; i++) {
        //printf("[%d]size : %lu \n", i, graph[i].size());
        sort(graph[i].begin(), graph[i].end(), compare);
    }
    dfs(R);
    for(int i = 1; i <= N; i++) {
        printf("%d\n", result[i]);
    }

    return 0;
}