10159 저울

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

모든 정점에 대하여 플로이드를 돌리고 비교 관계를 확인한다. 두 정점에 대하여 앞쪽이 더 큰지, 뒤쪽이 더 큰지 둘다 알 수 없다면 비교 관계를 알 수 없다.

#include <cstdio>
 
int n,m,i,j,k,d[101][101];
 
int main()
{
    scanf("%d %d",&n,&m);
    while(m--) scanf("%d %d",&i,&j),d[i][j]|=1;
    for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++)
        d[i][j]|=d[i][k]&d[k][j];
    for(i=1;i<=n;i++)
    {
        int cnt=0;
        for(j=1;j<=n;j++) if(!d[i][j] && !d[j][i]) cnt++;
        printf("%d\n",cnt-1);
    }
    return 0;
}