11400 썸네일형 리스트형 [python] baekjoon 11400 : 단절선 문제 -> 문제 링크 : https://www.acmicpc.net/problem/11400 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A www.acmicpc.net 문제풀이 단절선은 제거했을 때 그래프가 여러 개로 나눠지는 간선을 의미한다. 단절선 문제를 해결하기 위해서는 트리의 부모, 자식의 개념을 이용하면 쉽다. dfs를 이용해 방문 순서대로 정점에 순서를 매긴다고 하자. 이때 자식의 정점 순서는 부모의 정점 순서 + 1이 된다. 이때 현재 간선이 없다고 가정하고, 자식 정점에서부터 접근 가능한 모든 .. 더보기 이전 1 다음