글 읽기 - python3 시간초과 납니다...

dk41245 4년 전 0

시간초과가 발생한다면 dfs에서 발생할 것 같은데 정확한 이유를 모르겠습니다.

from sys import stdin


def update_graph(v1, v2, g):
    if v1 not in g:
        g[v1] = [v2]
    else:
        g[v1].append(v2)


def dfs(g, n):
    visited = [0 for _ in range(n+1)]
    dist = visited[:]
    for x in range(1, n+1):
        prev = 0
        if not visited[x]:
            stack = [x]
            while stack:
                vert = stack.pop()
                if not visited[vert]:
                    visited[vert] = 1
                    dist[vert] = dist[prev] + 1
                    if vert in g:
                        tmp = list(set(g[vert]) - set(visited))
                        stack += tmp
                prev = vert

    return dist


def chk(g, u):
    if u in g:
        arr = g[u]
        for x in arr:
            if (res[u] % 2) == (res[x] % 2):
                return False
    return True


t = int(input())
for q in range(t):
    n, m = map(int, stdin.readline().split())
    ans = []
    count = 0
    graph = {}
    for i in range(m):
        n1, n2 = map(int, stdin.readline().split())
        update_graph(n1, n2, graph)
        update_graph(n2, n1, graph)

    res = dfs(graph, n)

    for i in range(1, n+1):
        if not chk(graph, i):
            print("NO")
            break
    else:
        print("YES")

djm03178 4년 전 0

24번째 줄이 문제입니다. 정점 하나를 방문할 때마다 모든 정점에 대한 visited를 전부 확인하고 있어 O(N^2)이 되기 때문입니다.

dk41245 4년 전 0

그렇다면 탐색 방식을 재귀로 바꾸어야 할까요?

djm03178 4년 전 0

재귀로 하나 반복문으로 하나 똑같습니다. visit의 모든 원소를 안 보게끔 만들기만 하면 됩니다.

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

문제

문제

출처

ICPC

python3 시간초과 납니다...

dk41245 4년 전 0

djm03178 4년 전 0

dk41245 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말