정점 개와 간선 개로 이루어진 무향 그래프가 주어진다. 정점에는 의 번호가 붙어 있다.
두 정점 가 연결되어 있다는 것은, 에서 시작하여 간선을 따라 이동하는 것을 번 이상 반복해 에 도달할 수 있다는 뜻이다. 특히 모든 정점은 자기 자신과 연결되어 있다.
그래프에 새로운 무향 간선을 몇 개 추가하여, 모든 정점 쌍이 연결되어 있도록 만들고자 한다. 추가해야 하는 간선 개수의 최솟값을 구하여라.
입력은 다음과 같은 형식으로 주어진다.
첫째 줄에 추가해야 하는 간선 개수의 최솟값을 출력한다.
처음 그래프에는 와 , 두 개의 연결 컴포넌트가 있다. 두 컴포넌트 사이에 간선을 하나 추가하면 모든 정점이 서로 연결된다.
간선이 없으므로 개의 정점이 각각 하나의 연결 컴포넌트이다. 따라서 개의 간선이 필요하다.
이는 각 ()에 대해 와 를 잇는 무향 간선이 존재함을 의미한다.
| 3 | 55 | 추가적인 제약조건이 없다. |
처음부터 모든 정점이 서로 연결되어 있으므로 간선을 추가할 필요가 없다.
