BOJ : 1613 역사

문제 : https://www.acmicpc.net/problem/1613

github : https://github.com/JEONG-SEUNGWOOK/BOJ/blob/master/1613.cpp

i사건과 j사건의 연결고리를 검사하고 배열에 입력하고 마지막에 검사해 출력하는 형식으로 코드를 작성했다.

플로이드 와샬 알고리즘으로 해결.

입력이 400이기 때문에 연산횟수가 1억이 안넘지만 cin을 이용하면 TLE가 발생하고 scanf 사용하면 AC

이런 경우 때문에 scanf 사용하는 버릇이 생긴다

,

#include <cstdio>
using namespace std;

int n,k,s;
bool incident[401][401];
int main(){
    //cin사용하니 TLE
    scanf("%d%d",&n,&k);
    
    while(k--){
        int a,b;
        scanf("%d%d",&a,&b);
        incident[a][b]=true;
    }
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                incident[i][j] = incident[i][j] || (incident[i][k]&&incident[k][j]);
            }
        }
    }
    
    scanf("%d",&s);
    while(s--){
        int a,b;
        scanf("%d%d",&a,&b);
        if(!incident[a][b] && !incident[b][a]) printf("0\n");
        else if(incident[a][b]) printf("-1\n");
        else if(!incident[a][b] && incident[b][a]==1) printf("1\n");
    }
}