정올 #3428 백준 #17616 등수 찾기

백준 #17616
정올 #3426

백준 #2458 키 순서와 문제가 거의 같지만, 요구하는 출력값이 다르다.

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, m, x, a, b;
vector<int> higher[100001]; //i보다 높은 점수 가진 애들 배열
vector<int>lower[100001];//i보다 낮은 점수 가진 애들 배열
int chk_high[100001], chk_low[100001];
int cnt_low, cnt_high;
 
void high(int now){
    if(chk_high[now]) return; //방문했으면 리턴
    chk_high[now] = 1; //방문처리
    cnt_high++; //내가 아는 나보다 높은 등수인 사람 +1
    for(int i: higher[now]){
        high(i); //dfs 돌리기
    }
}
 
void low(int now){
    if(chk_low[now]) return;
    chk_low[now] = 1;
    cnt_low++;
    for(int i: lower[now]){
        low(i);
    }
}
 
int main(void){
    scanf("%d %d %d", &n, &m, &x);
    for(int i = 0; i<m; i++){
        scanf("%d %d", &a, &b);
        lower[a].push_back(b);
        higher[b].push_back(a);
    }
    high(x); low(x);
    printf("%d %d", cnt_high, n-cnt_low+1);
    //나보다 등수 높은 사람 = cnt_high명, 나보다 등수 낮은 사람 = cnt_low명
    //cnt_high < 내 등수 < n-cnt_low+1
    return 0;
 
}