poj 3660 Floyd 응용 (소의 위치 확인)

제목: N 개 선수, A 가 B 보다 강하 고 B 가 C 보다 강하 면 A 가 C 보다 강하 다.몇 명의 강약 관 계 를 알려 주 고 몇 명의 순 위 를 확정 할 수 있 느 냐 고 물 었 다.
사고: 만약 에 한 점 u 가 있 으 면 x 개의 점 이 이 점 에 도착 할 수 있 습 니 다. u 시 에서 출발 하여 y 개의 점 에 도착 할 수 있 습 니 다. 만약 에 x + y = N - 1 이 있 으 면 u 점 의 순 위 는 확정 적 입 니 다.flyd 로 두 점 사이 의 거 리 를 계산 하고 마지막 으로 통계 하면 dist [a] [b] 가 무한대 하고 dist [b] [a] 가 무한대 라면 a 와 b 의 순 위 는 확정 할 수 없다.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstdlib>
using namespace std;
#define INF 0x3fffffff
#define N 105
int g[N][N];
int n,m;
int main(){
    int i,j,k,a,b,res=0;
    scanf("%d %d",&n,&m);
    for(i = 1;i<=n;i++)
        for(j = 1;j<=n;j++)
            if(i!=j)
                g[i][j] = INF;
    for(i = 1;i<=m;i++){
        scanf("%d %d",&a,&b);
        g[a][b] = 1;
    }
    for(i = 1;i<=n;i++)
        for(j = 1;j<=n;j++)
            for(k = 1;k<=n;k++)
                g[j][k] = min(g[j][k],g[j][i]+g[i][k]);
    for(i = 1;i<=n;i++){
        for(j = 1;j<=n;j++)
            if(j!=i && g[i][j]==INF && g[j][i]==INF)
                break;
        if(j==n+1)
            res++;
    }
    printf("%d
",res);
    return 0;
}