무너지는 다리
다이아몬드 I의견: 0
정점이 \(N\)개인 무방향 그래프가 있다. 처음에는 간선이 하나도 없다.
이제 간선이 한 번에 하나씩, 총 \(Q\)개 추가된다. 각 간선이 추가될 때마다, 추가된 직후 그래프에 존재하는 다리(bridge)의 개수를 출력해야 한다.
다리란, 그 간선 하나를 제거했을 때 그 간선의 양 끝점이 서로 다른 연결 요소로 나뉘게 되는 간선을 말한다. 같은 두 정점 사이에 여러 개의 간선(중복 간선)이 추가될 수 있으며, 자기 자신으로의 간선은 주어지지 않는다.
간선은 오직 추가만 되고 절대 제거되지 않는다.
\(1 \le N \le 100{,}000\)
\(1 \le Q \le 100{,}000\)
첫 줄에 정점 수 \(N\)과 추가되는 간선의 수 \(Q\)가 주어진다.
이어서 \(Q\)개의 줄에 각각 두 정수 \(u\), \(v\)가 주어지며, 정점 \(u\)와 \(v\)를 잇는 간선이 추가됨을 뜻한다 (\(1 \le u, v \le N\), \(u \neq v\)).
각 간선이 추가된 직후의 다리 개수를 한 줄에 하나씩, 총 \(Q\)줄 출력한다.
4 4
1 2
2 3
3 4
1 4
1
2
3
0간선 1-2 추가 후 다리 1개. 2-3 추가 후 2개. 3-4 추가 후 3개(일자 경로). 마지막 1-4를 추가하면 사이클 1-2-3-4-1이 닫혀 모든 간선이 더 이상 다리가 아니므로 0개.
4 3
1 2
3 4
2 3
1
2
31-2 추가 후 다리 1개. 3-4 추가 후 서로 떨어진 두 다리로 2개. 2-3을 추가하면 네 정점이 하나의 경로로 이어져 다리가 3개가 된다.
플래티넘 IIIriseoj 작성
출처 Original
평가 및 의견
무너지는 다리
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
무너지는 다리