[백준 20955] 민서의 응급 수술 (C++)

이 문제는 그래프가 주어졌을 때, 그래프를 트리로 만들기 위한 최소 연산 횟수를 구하는 문제이다.

그래프가 연결 그래프가 아닐 수 있기 때문에, 분리 집합은 연결이 필요하고, 사이클이 발생하지 않도록 간선을 끊어주어야 한다.

분리 집합의 갯수는 그래프 탐색 기법을 통해 쉽게 구현이 가능하다. 방문 여부를 기록하는 vis배열을 통해 방문하지 않았으면 그래프 탐색의 시작점으로 지정하면 되고, 그래프에 속하는 정점들을 방문해가면서 vis배열을 업데이트 해줄 때, vis[i]가 false이면, 분리 집합으로 간주할 수 있다. 따라서, 해당 정점을 시작점으로 그래프 탐색을 반복하면 된다.

이렇게 분리 집합의 갯수인 cnt는 손쉽게 구할 수 있다.

먼저, 해당 그래프를 연결 그래프로 만들어준다고 가정하자. 그렇다면 연결시 연산 횟수는 cnt - 1이 된다.
이제, 연결 그래프가 되면서 간선을 cnt - 1개 추가했으므로 총 간선 수는 m + cnt - 1이 된다.

이제 사이클이 생기지 않도록 간선을 제거해야 한다.

우리는 어떤 간선이 제거되어야 하는지는 관심이 없다. 그저, 트리의 성질처럼 연결 그래프이면서 간선의 갯수가 n - 1이면 될 뿐이다.

따라서, 제거해야되는 간선의 갯수는 (m + cnt - 1) - (n - 1)가 된다.

연산의 총 횟수는 추가해야하는 간선 수 + 제거해야하는 간선 수 이므로, (cnt - 1) + ((m + cnt - 1) - (n - 1))임을 확인할 수 있다.

#include <bits/stdc++.h>
using namespace std;

int n, m, cnt;
vector<int> adj[100'001];
bool vis[100'001];

void dfs(int cur) {
	vis[cur] = 1;
	for (int nxt : adj[cur]) {
		if (vis[nxt]) continue;
		dfs(nxt);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0, u, v; i < m; i++) {
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	for (int i = 1; i <= n; i++) {
		if (vis[i]) continue;
		dfs(i);
		cnt++;
	}
	cout << (cnt - 1) + ((m + cnt - 1) - (n - 1));
}