역사

1. 개요

• https://www.acmicpc.net/problem/1613

2. 잘못된 위상정렬 풀이

import sys
from collections import deque

def solution():
    READLINE = lambda: sys.stdin.readline().rstrip()
    READINT = lambda: int(READLINE())
    READINTS = lambda: list(map(int, READLINE().split()))

    N, K = READINTS()
    ORDERS = [[v-1 for v in READINTS()] for _ in range(K)]

    S = READINT()
    SEARCH = [[v-1 for v in READINTS()] for _ in range(S)]

    DEPTH, P, G = [0]*(N), [i for i in range(N)], [[] for _ in range(N)]
    TOPOLOGYIDX = [0]*(N)

    def init():
        for s, e in ORDERS:
            DEPTH[e] += 1
            G[s].append(e)

    def parent(v):
        if v!=P[v]:
            P[v] = parent(P[v])
        return P[v]
        
    def union(a, b):
        pa, pb = parent(a), parent(b)

        if pa<pb:
            P[pb] = pa
        else:
            P[pa] = pb

        return True
        
    def topology():
        q, order = deque(), []
        
        for node in range(N):
            if DEPTH[node]==0:
                q.append(node)

        while q:
            node = q.popleft()
            order.append(node)

            for newNode in G[node]:
                DEPTH[newNode] -= 1
                
                if DEPTH[newNode]==0:
                    union(node, newNode)
                    q.append(newNode)

        for i, v in enumerate(order):
            TOPOLOGYIDX[v] = i

    def answer():
        result = []

        for a, b in SEARCH:
            if parent(a)!=parent(b):
                result.append("0")
            elif TOPOLOGYIDX[a]<TOPOLOGYIDX[b]:
                result.append("-1")
            else:
                result.append("1")

        print("\n".join(result))
        
    init()
    topology()
    answer()

solution()

3. 플로이드 와샬 알고리즘 활용 풀이

import sys

def solution():
    READLINE = lambda: sys.stdin.readline().rstrip()
    READINT = lambda: int(READLINE())
    READINTS = lambda: list(map(int, READLINE().split()))
    N, K = READINTS()

    CONNECTS = [READINTS() for _ in range(K)]
    CASES = [READINTS() for _ in range(READINT())]
    
    D = [[0]*(N+1) for _ in range(N+1)]
    
    # init
    for s, e in CONNECTS:
        D[s][e] = 1

    # washel
    for mid in range(1, N+1):
        for start in range(1, N+1):
            for end in range(1, N+1):
                if D[start][mid] and D[mid][end]:
                    D[start][end] = 1

    answer = []
    for start, end in CASES:
        if D[end][start]==1:
            answer.append("1")
        elif D[start][end]==1:
            answer.append("-1")
        else:
            answer.append("0")
            
    print("\n".join(answer))

solution()