1613번

1613번 - 역사

단순 플로이드 알고리즘을 이용해서, 주어진 값이 연결이 되어있는지 안되어있는지를 확인하면 됐다.

양방향 간선이 아니기 때문에 간단하게 풀 수 있었는데..

너무 복잡하게 생각해서, 경로까지 만들어서 풀려다 보니 풀리지가 않았다..

처음에 생각을 정확하게 할 필요가 있다는 것을 느꼈다..

###

그래도 간만에 플로이드를 이용해서 path 를 만드는 법을 공부했다.

다시 한번 만드는 방법을 공부하고, 코딩으로 구현해봐야겠다.

<정답 코드>

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int a, b;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    //freopen("input.txt", "r", stdin);
    int n, k;
    cin >> n >> k;
    
    vector<vector<int>> v(n+1);
    vector < vector < bool >> D(n + 1, vector<bool>(n + 1, false));
    vector<vector<int>> via(n + 1, vector<int>(n + 1,-1));
    for (int i = 1; i <= n; i++)
    {
        D[i][i] = true;
    }
    while (k--)
    {
        int from, to;
        cin >> from >> to;
        v[from].push_back(to);
        D[from][to] = true;
    }
 
 
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                D[i][j] = D[i][j] || D[i][k]&&D[k][j];    
            }
        }
    }
 
    
    int s;
    cin >> s;
    while (s--)
    {    
        cin >> a >> b;
        if (D[a][b])
        {
            cout << "-1\n";
            continue;
        }
 
        if (D[b][a])
        {
            cout << "1\n";
            continue;
        }
 
        cout << "0\n";
    }
    return 0;
}