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

[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:])

from http://devlibrary00108.tistory.com/559 by ccl(A) rewrite - 2021-10-03 05:00:58