[백준 17616] 등수 찾기

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

17616번: 등수 찾기

 

두 학생 중 어느 학생의 등수가 더 높은지, 상대적인 정보만을 가지고 특정 학생이 가질 수 있는 등수의 범위를 찾아 최대, 최소를 구하는 문제이다. 구하고자 하는 학생을 기준으로, 등수가 높은 학생과 낮은 학생의 수를 각각 BFS를 활용하여 구한 후, 이를 바탕으로 가능한 가장 높은 등수, 낮은 등수를 구했다.

( 가능한 가장 높은 등수 : 1 + 자신보다 높은 학생 수, 가능한 가장 낮은 등수 : n- 자신보다 낮은 학생 수) 

 

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

int n,m,x;
vector<int> smaller[100001];
vector<int> bigger[100001];
bool visited[100001];

int main(){
    cin>>n>>m>>x;
    for (int i = 0; i < m; i++) {
        int a,b;
        cin>>a>>b;
        smaller[a].push_back(b);
        bigger[b].push_back(a);
    }
    queue<int> q;
    int smallerCnt=0;
    visited[x]=true;
    q.push(x);
    while (!q.empty()) {
        int tmp = q.front();
        q.pop();
        for (int i = 0; i < smaller[tmp].size(); i++) {
            int x = smaller[tmp][i];
            if(!visited[x]) {
                q.push(x);
                visited[x] = true;
                smallerCnt++;
            }
        }
    }

    int biggerCnt=0;
    q.push(x);
    while (!q.empty()) {
        int tmp = q.front();
        q.pop();
        for (int i = 0; i < bigger[tmp].size(); i++) {
            int x = bigger[tmp][i];
            if(!visited[x]) {
                q.push(x);
                visited[x] = true;
                biggerCnt++;
            }
        }
    }

    cout << 1 + biggerCnt << " " << n - smallerCnt;

}