[백준] 키 순서 (C++)

문제 링크: www.acmicpc.net/problem/2458

2458번: 키 순서

1. 주의할 점

- 한 학생이 자신의 순서를 정확히 아는 경우: 앞에서 몇번째인지 + 뒤에서 몇번째인지

 

2. 구현

- 모든 순서에 대한 정보를 V[] 벡터에 담는다. 이때, 앞에 나온 수 V[A]에 뒤에 나온 수 B를 추가한다

- 모든 학생들에 대해서 단방향 BFS를 수행하며 해당 학생이 몇명의 다른 학생에게 도달이 가능한지(자기보다 큰 사람)를 canReach[]++를 통해 저장하며, 도달당한 학생은 몇명의 학생들에게 도달당했는지를 canBeReached[]++를 통해 저장한다

- 모든 학생에 대해 단방향 BFS가 끝났다면 한 학생이 자신을 제외한 나머지 학생들에게 도달 가능하거나 도달당할 수 있다면 Cnt++를 한다

- Cnt를 출력한다

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> v[501];
bool check[501];
int canBeReached[501];
int canReach[501];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int node,edge,a,b,cnt=0;
    cin >>node>>edge;
    for(int i=0;i<edge;i++){
        cin >> a>> b;
        v[a].push_back(b);
    }
    for(int k=1;k<=node;k++){
        queue<int> q;
        q.push(k);
        for(int i=1;i<=node;i++)
            check[i]=false;
        check[k]=true;
        
        while(!q.empty()){
            int cidx = q.front();
            q.pop();
            for(int i=0;i<v[cidx].size();i++){
                int next = v[cidx][i];
                if(check[next]) continue;
                check[next]=true;
                q.push(next);
                canReach[k]++;
                canBeReached[next]++;
            }
        }
    }
    for(int i=1;i<=node;i++){
        int sum = canBeReached[i]+canReach[i];
        if(sum==node-1)
            cnt++;
    }
    cout<<cnt;
    return 0;
}