백준 2458 키 순서 C++

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

모든 노드의 연결 관계를 파악해야한다.

n 이 500이므로 플로이드 와샬을 사용할 수 있고, 모든 정점으로부터 다른 모든 정점까지의 비용을 파악할 수 있다.

비용은 1로 두고, 갈 수 있는지 없는지만 파악하면 된다.

주의할 사항은, degree를 계산할 때, 자신에서 자신으로 가는 것은 카운트하지 않아야 한다는 것이다.

자기 자신으로의 경로 비용 초기화를 어떻게 했는지에 따라 잘 처리해주면 되겠다.

#include<iostream>
#include<algorithm>
#define INF 100000000
using namespace std;
int map[501][501], m, n, degree[501];
void FW() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
            }
        }
    }
 
    // 노드 i까지 갈 수 있는 노드의 수 + 노드 i에서 갈 수 있는 노드수
    // 이게 n-1이면 됨. degree 계산
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (map[i][j] != INF && i != j) {
                degree[i]++;
                degree[j]++;
            }
        }
    }
}
int main(void) {
    cin >> n >>m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            map[i][j] = i==j ? 0 : INF;
        }
 
    for (int i = 0; i < m; i++) {
        int src, dst;
        cin >> src >> dst;
        map[src][dst] = 1;
    }
    FW();
    int res = 0;
    for (int i = 1; i <= n; i++)
        if (degree[i] == n - 1) res++;
    cout << res;
    return 0;
}
 
//n이 500 -> 행렬에 다 넣어도 됨
//비용 1로두고 플와 돌려서 모든 간선 연결 및 비용 파악