본문 바로가기

146751

BOJ 14675 ) 단절점과 단절선 14675번: 단절점과 단절선 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정 www.acmicpc.net 주어진 트리에서 쿼리로 주어지는 정점과 간선이 해당 트리의 단절점 또는 단절선 인지(없을 경우 트리가 둘로 나뉘는지)를 묻는 문제이다. 한학기만에 알고리즘 문제를 풀었는데 너무 오랜만이라 완전히 방향을 잘못 잡았다. 고질병인 시간복잡도 계산 안하고 일단 문제 풀기는 여전히 고쳐지지 않았다. 정점의 개수 10만에 쿼리가 10만갠데 매 쿼리마다 dfs를 돌렸고 당연히 시간초과가 났다. 생각해보니까 당연한거였는데 왜 짤때는 모르는걸까. 주어진.. 2020. 9. 19.

이전 1 다음

티스토리툴바