2458 키 순서

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

먼저 플로이드를 돌려서 모든 정점 사이의 거리를 구한다. 그리고 정점 i에서 다른 정점 j에 대해서 하나라도 d[i][j], d[j][i] 모두 알 수 없다면 자신의 키 순서를 정확히 알 수 없다.

#include <cstdio>
#define INF 987654321
 
int n,m,a,b,i,j,k,ans,d[501][501];
 
int main()
{
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++) for(j=1;j<=n;j++) d[i][j]=i==j?0:INF;
    while(m--) scanf("%d %d",&a,&b),d[a][b]=1;
    for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++)
        if(d[i][j]>d[i][k]+d[k][j]) d[i][j]=d[i][k]+d[k][j];
    for(i=1;i<=n;i++)
    {
        int f=1;
        for(j=1;j<=n;j++)
        {
            if(d[i][j]==INF && d[j][i]==INF)
            {
                f=0;
                break;
            }
        }
        if(f) ans++;
    }
    printf("%d\n",ans);
    return 0;
}