[C++]백준 2458번 키 순서

📌문제 링크

---

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

📌문제 설명

---

학생들의 키 순서를 그래프로 표현하고 특정 학생의 키가 다른 학생들과 비교했을 때 몇 번째인지 알 수 있는지를 구하는 문제입니다. input() 함수는 학생 수(N)와 비교 횟수(M)를 입력받고, 각 비교 결과를 그래프로 저장합니다. init() 함수는 방문 배열과 카운터를 초기화합니다. dfs(int idx)와 reverseDfs(int idx) 함수는 각각 깊이 우선 탐색(DFS)과 역방향 DFS를 수행하여 그래프를 탐색합니다. solve() 함수는 각 학생에 대해 DFS와 역방향 DFS를 수행하여 키 순서를 계산하고, 결과를 출력합니다. 이 코드는 그래프 탐색을 통해 학생들의 키 순서를 계산하고, 특정 학생의 키가 다른 학생들과 비교했을 때 몇 번째인지 알 수 있도록 합니다.

📌코드

---

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> graph[501], reverseGraph[501];
bool visited[501];
int N, M, a, b, answer, cnt;

void input(){
    cin >> N >> M;
    for(int i = 0; i < M; i++){
        cin >> a >> b;
        graph[a].push_back(b);
        reverseGraph[b].push_back(a);
    }
}

void init(){
    fill(&visited[0], &visited[501], false);
    cnt = 0;
}

void dfs(int idx){
    visited[idx] = true;
    for(auto it : graph[idx]){
        if(visited[it]){
            continue;
        }
        cnt++;
        dfs(it);
    }
}

void reverseDfs(int idx){
    visited[idx] = true;
    for(auto it : reverseGraph[idx]){
        if(visited[it]){
            continue;
        }
        cnt++;
        reverseDfs(it);
    }
}

void solve(){
    input();
    for(int i = 1; i <= N; i++){
        int temp = 0;

        init();
        dfs(i);
        temp += cnt;

        init();
        reverseDfs(i);
        temp += cnt;
        
        if(temp == N - 1){
            answer++;
        }
    }
    cout << answer;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}