글 읽기 - 시간 초과가 되는 이유가 궁금합니다.

tkddnjs45682 1년 전 0

타잔 알고리즘으로 SCC를 구하는 문제입니다. 일주일 째 알고리즘 공부해보면서 구현을 해보고 있는데, 도대체 어떤 부분 때문에 시간 초과가 나는지 모르겠습니다...

시간 초과가 날만한 부분이 어느 부분일까요... 아무리 생각해도 O(V+E)를 넘길 가능성이 있는 부분이 sorting 부분 정도밖에 안 떠오르는데, 문제 출력 조건이 sorting이 필요한 부분이라 이를 없앨 수도 없을 것 같다고 생각하는데, 어떤 부분일지 지적이라도 해주시면 너무 감사하겠습니다.

참고로 pypy로 돌리면 메모리 초과가 나옵니다!

from sys import setrecursionlimit, stdin
setrecursionlimit(10 ** 6)

def get_scc(V, graph):
    for k in range(1, V+1):
        if visited[k] == 0:
            dfs(graph, k)

    result.sort(key= lambda x : x[0])
    print(len(result))
    for scc in result:
        print(*scc, -1)

def dfs(graph, current_node):
    visited[current_node] = 1
    stack.append(current_node)
    global id_val
    id_val += 1
    ids[current_node] = id_val
    parent[current_node] = id_val

    for next_node in graph[current_node]:
        if visited[next_node] == 1:
            if not finished[next_node]:
                node_1 = next_node
                node_2 = current_node
                k = 0
                while node_2 != next_node:
                    parent[node_2] = min(parent[node_1], parent[node_2])
                    node_1 = node_2
                    node_2 = stack[-1-k]
                    k += 1

        else: # next node not visited
            dfs(graph, next_node)

    if parent[current_node] == ids[current_node]:
        popped = -1
        scc = []

        while popped != current_node:
            popped = stack.pop()
            scc.append(popped)
            finished[popped] = True
        result.append(sorted(scc))


## Main
V, E = map(int, stdin.readline().split())
graph = [[] for _ in range(V+1)] # 편의상 0번 인덱스는 그냥 가지고만 있는 것. 1~V번 node만 존재함.

for k in range(E):
    start, end = map(int, stdin.readline().split())
    graph[start].append(end)

id_val = 0
result = []
stack = []
visited = [0 for _ in range(V + 1)]
parent = [0 for _ in range(V + 1)]  # low link value
ids = [0 for _ in range(V + 1)]
finished = [False for _ in range(V + 1)]

get_scc(V, graph)

zenith82114 1년 전 0

제가 아는 Tarjan과 좀 다르네요.

28줄의 while이 각 SCC마다 크기만큼 돌아서 전체 O(V^2) 시간이 될 것 같은데

제가 기억하기로는 22줄 for문 안에 더 이상의 루프는 없어야 합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간 초과가 되는 이유가 궁금합니다.

tkddnjs45682 1년 전 0

zenith82114 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말