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

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

사용 언어: C++

 

풀이

무방향 그래프이므로 양쪽 인덱스에 넣어주고, 시작 노드부터 dfs를 돌린다.

dfs에서는 visited를 true로 해주고, 방문한 노드의 순서를 order로 저장하고, 오름차순 방문이므로 sort를 하고 다음 인접 노드가 방문하지 않은 노드면 재귀를 돌린다.

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

vector<int> graph[100001];  
bool visited[100001];       
int order[100001];          
int cnt = 1;                

void dfs(int node) 
{
    visited[node] = true;
    order[node] = cnt++;
    
    sort(graph[node].begin(), graph[node].end());
    
    for (int neighbor : graph[node]) 
    {
        if (!visited[neighbor]) 
        {
            dfs(neighbor);
        }
    }
}

int main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N, M, R;
    cin >> N >> M >> R;

    for (int i = 0; i < M; i++) 
    {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    dfs(R);

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

    return 0;
}