간선을 온라인으로 추가할 때 기존 bridge가 cycle로 사라지는 것은 어떤 경로의 간선들인가요?

새 간선이 이미 연결된 두 정점 u, v를 잇는다면, 기존 그래프에서 u와 v 사이에 있던 forest path의 간선들이 새 간선과 cycle을 이룹니다. 그 경로에 있던 bridge는 더 이상 bridge가 아닙니다. 예를 들어 bridge forest가 A-B-C이고 A-C를 추가하면 A-B와 B-C 각각에 우회 경로가 생겨 bridge count가 2개 줄어듭니다. 새 간선 자체도 cycle 안에 있으므로 bridge가 되지 않습니다.

반대로 u와 v가 서로 다른 연결 요소에 있다면 새 간선은 두 요소를 처음 연결하는 유일한 통로가 되어 bridge 하나를 추가합니다. 같은 연결 요소인지와 bridge-component forest에서 두 끝점의 경로가 무엇인지가 삽입 처리의 첫 분기입니다.

정적 low-link 배열을 한 번 계산해 두고 새 간선이 들어올 때 일부 low만 고치는 방식은 일반적으로 충분하지 않습니다. cycle이 forest path 전체의 bridge 상태를 바꾸기 때문입니다. 온라인 자료구조는 연결 요소용 DSU와 bridge-connected component forest를 유지하고, 같은 component를 연결할 때 path를 따라 component를 합치거나 reroot하는 전략을 사용합니다. 단, 구체적인 자료구조와 상환 복잡도는 별도 구현 계약으로 확인해야 합니다.

동일 요소 삽입에서 바뀌는 것은 새 간선 하나가 아니라 forest path 전체입니다. 상태를 [A-B bridge, B-C bridge], count=2에서 시작해 A-C를 넣은 뒤 [A-B non-bridge, B-C non-bridge, A-C non-bridge], count=0으로 기록해야 합니다. 다른 요소의 B-X 삽입은 path가 없으므로 새 edge만 bridge입니다. self-loop는 u-v 경로를 만들지 않고 일반적으로 bridge가 아니며, 중복 간선은 첫 삽입으로 생긴 병렬 우회를 반영합니다. DSU는 연결 여부를, bridge-component forest는 아직 bridge인 component 연결을 표현하므로 하나로 합치면 안 됩니다. reroot와 path compression의 구체 비용은 자료구조 구현에 달렸지만 cycle에 포함된 경로 전체를 해제한다는 불변식은 변하지 않습니다.