백준 24484 - 알고리즘 수업 - 깊이 우선 탐색 6(C++)

문제 링크입니다. https://www.acmicpc.net/problem/24484

24484번: 알고리즘 수업 - 깊이 우선 탐색 6

 

 

해당 문제에서 내림차순을 해주면 되는 문제입니다. 자세한 설명은 해당 글을 참고해주세요.

https://junseok.tistory.com/298

백준 24483 - 알고리즘 수업 - 깊이 우선 탐색 5(C++)

 

 

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second
#define LL long long int

using namespace std;

int N, M, R;
vector<int> connect[100001];
LL check[100001];
LL depth[100001];
int Count = 1;

bool cmp(int x, int y){
    if(x > y) return true;
    else return false;
}

void dfs(int x, int cnt){
    depth[x] = cnt;
    check[x] = Count++;
    for(int i = 0 ; i < connect[x].size(); i++){
        int xx = connect[x][i];
        if(check[xx] != 0) continue;
        dfs(xx, cnt + 1);
    }
}

void solve(){
    LL sum = 0;
    for(int i = 1; i <= N; i++){
        sort(connect[i].begin(), connect[i].end(), cmp);
    }
    memset(depth, -1, sizeof(depth));
    dfs(R, 0);
    for(int i = 1; i <= N; i++){
        sum += check[i] * depth[i]; 
    }
    cout << sum;
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M >> R;
    for(int i = 1; i <= M; i++){
        int x, y;
        cin >> x >> y;
        connect[x].push_back(y);
        connect[y].push_back(x);
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요