[Codefroce][Python] div.3 #731 - G. How Many Paths?

싸이클을 지나는 경로에 속한 노드들에 대해 처리하는 문제입니다.

아직 scc에 대해 익숙하지 못해 TLE상태입니다.

현 로직은 dfs를 통해 방문 횟수를 check해 0, 1, 2상태에 대해서 처리 한 후

cycle에 속한 요소를 찾았다면 각 요소들에 대해 dfs로 순회해주며

이미 -1 처리되었다면 return하는 백트래킹까지 해주었습니다.

아직 7번째 test set에서 TLE상태라 조금 더 보완하겠습니다.

 

import sys
input = sys.stdin.readline


# 1부터 탐색. cycle생기면 cycle에 포함되는 요소 하나 check.
def dfs(cur_node, path):
    if answer[cur_node] < 2:
        answer[cur_node] += 1
    for next_node in graph[cur_node]:
        if path & (1 << next_node):
            cycle.append(next_node)
        else:
            dfs(next_node, path | (1 << next_node))


# cycle요소로부터 갈 수 있는 모든 요소들 -1로 바꿈(infinite기 때문)
def dfs2(cur_node, path):
    if answer[cur_node] == -1:
        return
    answer[cur_node] = -1
    for next_node in graph[cur_node]:
        if not path & (1 << next_node):
            dfs2(next_node, path | (1 << next_node))


for test in range(int(input())):
    input()
    n, m = map(int, input().split())
    cycle = []
    graph = {i: [] for i in range(1, n + 1)}
    answer = [0] * (n+1)
    for _ in range(m):
        a, b = map(int, input().split())
        graph[a] += [b]
    # 못가면 0, 1, 2(경로 1개 초과), -1(경로 사이에 사이클 있으면)
    dfs(1, 1)
    for infinite in cycle:
        dfs2(infinite, (1 << infinite))
    print(*answer[1:])