글 읽기 - 백간선 알고리즘을 논리적으로 구현한 것 같은데 어느 부분이 틀린지 모르겠습니다.

papayetoo 3년 전 0

4 3

1 2

2 3

2 4

----

7 6

1 2

2 3

2 4

2 5

5 6

5 7

----

8 7

1 2

1 3

2 4

2 5

3 6

3 7

4 8

----

문제 예제 외에도 위에 기재한 테스트 케이스로 맞은 코드와 아래 다시 작성한 코드로 돌렸을 때, 같은 결과가 나와서 맞다고 생각했는데 제가 생각하지 못한 반례나 제 코드에 논리적으로 틀린 부분이 있는 거 같은데 어디가 있을 까요?

# 단절점 찾기 - articulation point
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 9)


class Solution:
    def findArticulationPoint(self):
        v, e = map(int, sys.stdin.readline().split())
        graph = defaultdict(list)
        # 무방향 그래프 생성
        for _ in range(e):
            u, w = map(int, sys.stdin.readline().split())
            graph[u].append(w)
            graph[w].append(u)

        dfn = [None] * (v + 1)
        low = [float('inf')] * (v + 1)
        ap = [False] * (v + 1)
        count = 0

        def dfs(node: int, count: int):
            nonlocal dfn, ap
            dfn[node] = count
            children = 0
            ret = dfn[node]

            for nextNode in graph[node]:
                if dfn[nextNode] is not None:
                    ret = min(ret, dfn[nextNode])
                else:
                    children += 1
                    subtree = dfs(nextNode, count + 1)
                    if count != 1 and subtree >= dfn[node]:
                        ap[node] = True
                    ret = min(ret, subtree)

            if count == 1 and children >= 2:
                ap[node] = True

            return ret

        dfs(1, 1)
        answer = [i for i, ap in enumerate(ap) if i > 0 and ap]
        print(len(answer))
        print(*answer)


if __name__ == '__main__':
    sol = Solution()
    sol.findArticulationPoint()

papayetoo 3년 전 0

문제에서 연결 그래프가 아닐 수 있다라는 조건을 제대로 읽지 않아서 발생한 문제였고,

dfs(1,1) 부분을 수정해서 해결했습니다.

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

문제

문제

출처

ICPC

백간선 알고리즘을 논리적으로 구현한 것 같은데 어느 부분이 틀린지 모르겠습니다.

papayetoo 3년 전 0

papayetoo 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말