연결성이란 그래프에서 임의의 두 정점 간에 이동할 수 있는 경로가 있을 경우 두 정점 간에 연결성이 존재한다는 것이다. 만약 임의의 간선을 제거했을 경우 그래프 상의 임의의 두 정점간의 연결성이 바뀌는 경우가 하나라도 존재할 경우에는 이러한 간선을 브릿지라고 한다.

위와 같은 그래프에서 A와 B를 잇는 간선을 제거하였을 경우 A와 다른 정점간의 연결성이 사라지게 되며, 따라서 A와 B를 잇는 간선은 브릿지라고 할 수 있다.

주어진 그래프에서 브릿지가 모두 몇 개인지 세는 프로그램을 작성하라.

브릿지 세기 timer 2s memory - MB

브릿지 세기 2s - MB