2458번

2458번 - 키순서

플로이드 알고리즘 문제. N제한이 500이라 시간 초과가 뜨지 않도록 아래부분도 추가했다.

    ios::sync_with_stdio(false);

    cin.tie(NULL);

로직은

나보다 키 큰 사람의 숫자, 나보다 키 작은 사람의 숫자가 총 인원과 같으면 나의 키를 알 수 있다.

따라서 플로이드 알고리즘으로 D배열을 구한 뒤,

나보다 키 큰 사람의 숫자 = D[나][다른사람]

나보다 키 작은 사람의 숫자 = D[다른사람][나] 

일 때 마다 숫자를 세서 문제를 풀면 된다.

<정답 코드>

#include<iostream>
#include<vector>
using namespace std;
 
int main()
 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    //freopen("input.txt", "r", stdin);
    int n, m;
    cin >> n >> m;
    vector<vector<bool>> D(n + 1, vector<bool>(n + 1, false));
    for (int i = 1; i <= n; i++)
    {
        D[i][i] = true;
    }
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        D[a][b] = true;
    }
 
 
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                D[i][j] = D[i][j] || (D[i][k] && D[k][j]);
            }
        }
    }
    int cnt = 0;
    vector<int> check(n + 1,0);
    for (int from = 1; from <= n; from++)
    {
        for (int to = 1; to <= n; to++)
        {
            if (D[from][to])
            {
                check[from]++;
                continue;
            }
 
            if (D[to][from])
            {
                check[from]++;
                continue;
            }
        }
    }
    
    for (int i = 1; i <= n; i++)
    {
        if (check[i] == n)
        {
            cnt++;
        }
    }
 
    cout << cnt << "\n";
 
    return 0;
}