백준 1613번: 역사

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

1613번: 역사

 

 문제 설명 

 

1. 각 사건을 번호로 표시하고 사건의 순서가 주어진다.

2. 순서를 입력후 전후 관계를 알고 싶은 사건이 입력되었을때 앞에 있는 번호의 사건이 먼저 일어났으면 -1,

  뒤에 있는 번호의 사건이 먼저 일어났으면 1, 어떤지 모르면 0을 출력.

 

 알고리즘 

 

1. 배열에 순서관계를 입력 받을 때  a , b순으로 입력받을경우 map[a][b]=-1 ,map[b][a]=1 로 초기화 한다.

2. 플루이드 알고리즘으로 순서관계를 정리한다.

3. 전후 관계를 알고싶은 곳의 배열 값을 출력한다.

 

 코드 

 

#include<iostream>
#include<algorithm>
 
 
using namespace std;
 
int map[401][401];
int N, M;
 
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    cin >> N >> M;
 
    //배열 초기화
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            map[i][j] = 0;
        }
    }
 
    
    for (int i = 0; i <M; i++) {
            int a, b;
            cin >> a >> b;
            map[a-1][b-1] = -1;
            map[b-1][a-1] = 1;
    }
 
 
    //플루이드 알고리즘
    for(int k=0;k<N;k++){
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == j)continue;
 
            if (map[i][j] == 0) {
                if (map[i][k] == 1 && map[k][j] == 1)
                {
                    map[i][j] = 1;
                }
                else if (map[i][k] == -1 && map[k][j] == -1)
                {
                    map[i][j] = -1;
                }
            }
 
            
        }
    }
    }
 
    int k;
    cin >> k;
    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;
        cout << map[a - 1][b - 1]<<"\n";
    }
 
 
 
}