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

문제 출처: https://www.acmicpc.net/problem/24479

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

정점의 수가 10만이기 때문에 배열을 사용할 수 없다.

인접 리스트를 이용하여 탐색해야 하기 때문에 오름차순으로 정렬을 해야한다.

이후 DFS 탐색을 진행한다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include <string>
#include <math.h>

using namespace std;


int N, M, R;
vector <int> adj[100001];
int visited[100001];
int Count = 1;

void dfs(int node) {
    
    for (auto next : adj[node]) {
        if (visited[next] != 0)continue;
        visited[next] = Count++;
        dfs(next);
    }
}


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

    cin >> N >> M >> R;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    for (int i = 0; i <= N; i++) {
        sort(adj[i].begin(), adj[i].end());
    }
    
    visited[R] = Count++;
    dfs(R);

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

}