10159번

10159번 - 저울

저울의 크기 비교하는 문제인데, 노드로 나타내면, 방향 그래프로 나타낼 수 있다는 점을 알 수 있다.

따라서 각 쌍이 연결이 되어있는지 여부를 파악하는 플로이드 알고리즘을 통해 풀 수 있다.

플로이드 알고리즘에서 for문 3개 중, 가장 바깥 쪽이 k 인데,

맨 처음에 풀 때, 가장 안쪽을 k 로 해서 틀렸었다.

플로이드 알고리즘 정확히 기억하기!

<정답 코드>

#include<iostream>
#include<vector>
 
using namespace std;
const int INF = 987654321;
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    vector<vector<bool>> D(n + 1, vector<bool>(n + 1, false));
    for (int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d%d", &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]);
            }
        }
    }
 
    for (int i = 1; i <= n; i++)
    {
        int ans = 0;
        for (int j = 1; j <= n; j++)
        {
            if (!D[i][j] && !D[j][i] && i!=j)
            {
                ans++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}