Connecting a Graph

그래프의 연결 컴포넌트 개수를 $K$라 하자.

서로 다른 두 연결 컴포넌트 사이에 간선을 하나 추가하면, 두 컴포넌트가 하나로 합쳐진다. 따라서 연결 컴포넌트 개수는 한 번의 간선 추가로 최대 $1$만 줄어든다. 모든 정점이 서로 연결되려면 컴포넌트가 하나만 남아야 하므로, 적어도 $K-1$개의 간선이 필요하다.

반대로, 각 연결 컴포넌트에서 대표 정점을 하나씩 고르고, 이 대표 정점들을 임의의 순서로 일렬로 연결하면 정확히 $K-1$개의 간선으로 전체 그래프가 연결된다. 그러므로 정답은 $K-1$이다.

연결 컴포넌트 개수는 분리 집합 자료구조를 이용하여 구할 수 있다. 처음에는 모든 정점이 서로 다른 집합에 속한다고 두고, 입력으로 주어진 각 간선 $(u_i,v_i)$에 대해 두 정점이 속한 집합을 합친다. 마지막에 서로 다른 대표자의 개수를 세면 $K$를 얻는다.

시간 복잡도는 $O((N+M)\alpha(N))$이다.

Solution written by GPT5.5