[백준 2458] 키 순서 C++

2458번: 키 순서

 

플로이드-와샬

---

1. 문제 해결 아이디어

 

자신보다 키가 큰 게 확실한 사람, 키가 작은 게 확실한 사람들의 수를 구하면 된다.

주어진 방향그래프에서 자신이 도달할 수 있는 정점들이 모두 자신보다 키가 큰 학생임을 알 수 있다.

자신보다 키가 작은 학생들도 알아야 하므로 입력이 주어질 때 역방향 그래프도 같이 저장한다.

역방향 그래프에서 자신이 도달할 수 있는 정점들이 모두 자신보다 키가 작은 학생임을 알 수 있다.

 

따라서 임의의 정점에서 다른 모든 정점으로 갈 수 있다면 모든 사람과 키를 비교할 수 있으므로 자신의 키가 몇 번째인지 알 수 있다.

---

2. 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N, M;
int adj[501][501][2];
 
void input(){
    cin >> N >> M;
    int a, b;
    
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            if(i == j) continue;
            adj[i][j][0] = INF;
            adj[i][j][1] = INF;
        }
    }
    
    for(int i = 0; i < M; i++){
        cin >> a >> b;
        adj[a][b][0] = 1;
        adj[b][a][1] = 1;
    }
}
 
void solve(){
    for(int i = 1; i <= N; i++){
        for(int r = 1; r <= N; r++){
            for(int c = 1; c <= N; c++){
                adj[r][c][0] = min(adj[r][i][0] + adj[i][c][0], adj[r][c][0]);
                adj[r][c][1] = min(adj[r][i][1] + adj[i][c][1], adj[r][c][1]);
            }
        }
    }
    
    int answer = 0;
    for(int i = 1; i <= N; i++){
        bool find = true;
        for(int j = 1; j <= N; j++){
            if(adj[i][j][0] == INF && adj[i][j][1] == INF){
                find = false;
                break;
            }
        }
        if(find) answer++;
    }
    
    cout << answer;
}
 
int main(){
    fasti
    input();
    solve();
    
    return 0;
}