[2458] 키 순서

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

2458번: 키 순서

현재 정점이 자신의 키가 몇번째인지를 알수 있는가는, 플로이드를 이용해서 dst를 구한 뒤

현재 정점을 제외한 모든 정점이, 현재 정점에서 다른 정점으로 도달 가능 하거나(dst[cur][i] < INF)

다른 정점에서 현재 정점으로 도달 가능해야 한다. (dst[i][cur] < INF)

 

아이디어는 골4치곤 좀 어려운 느낌이다. 플로이드 태그는 스탠다드 난이도가 없어서 난이도 매기기가 애매한듯 싶다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

int n, m, a[501][501];

constexpr int INF = 1e9;

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n >> m;

    int i, j, k;

    for (i = 1; i <= n; i++)

        for (j = 1; j <= n; j++) a[i][j] = (i == j) ? 0 : INF;

    for (i = 0; i < m; i++) {

        int A, B;

        cin >> A >> B;

        a[A][B] = 1;

    }

    for (k = 1; k <= n; k++)

        for (i = 1; i <= n; i++)

            for (j = 1; j <= n; j++) a[i][j] = min(a[i][k] + a[k][j], a[i][j]);

    int ans = 0;

    for (i = 1; i <= n; i++) {

        int cur = 0;

        for (j = 1; j <= n; j++)

            if (a[i][j] < INF || a[j][i] < INF) cur++;

        if (cur == n) ans++;

    }

    cout << ans;

    return 0;

}

---