코드 복사/붙여넣기 하는 당신이 아름답습니다.

10159 : 저울

풀이

a와 b의 대소관계를 알 수 있다는 것은

a에서 b까지 알고 있는 관계를 건너건너 도착할 수 있다는 것이고

n 제한이 100으로 엄청 작으므로 모든 경로를 구해놓자.

그리고 도달할 수 없는 노드의 개수를 세어주자.

코드

#include <stdio.h>
int n, m, a[101][101];
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0, x, y; i < m; i++)
        scanf("%d %d", &x, &y), a[x][y] = 1;
    
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (a[i][k] && a[k][j]) a[i][j] = 1;
    
    for (int i = 1; i <= n; i++) {
        int ans = -1;
        for (int j = 1; j <= n; j++)
            if (!a[i][j] && !a[j][i]) ans++;
        printf("%d\n", ans);
    }
    
    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-09-17 00:14

Read more posts by this author