[BOJ/20955] 민서의 응급 수술, c++

www.acmicpc.net/problem/20955

20955번: 민서의 응급 수술

한줄 후기: 수술은 의사에게..

 

그래프 문제처럼 보인다.

처음의 mst 관련인가 하고 생각했는데 문제를 읽어보니 대충 연결 요소의 개수를 구해주면되는 거 아닌가? 하고 바로 코드를 작성했다.

틀렸다!

다시 문제를 읽어보니 민서가 할 수 있는 연산이 2개이다. 난 이중 뉴런끼리 연결을 끊는 연산을 간과했다.

 

뉴런끼리 연결을 끊어야만 하는 경우가 언제일까? 

사이클이다! 

민서는 트리를 만들고 싶어하는 것이니 사이클은 필히 지워주어야 한다. 

따라서 연결요소의 개수 -1 + 사이클 개수가 최소 연산 횟수가 된다.

(사이클에서 간선 하나만 지우면 되니까)

사이클 detect를 어찌할까 하다 union-find를 쓰려했는데 그냥 dfs 구현했던거에 코드를 추가해서 사이클을 감지했다.

 

//AC
//BOJ 20955 민서의 응급 수술
#include <iostream>
#include <vector>
using namespace std;
vector<int> v[101010];
bool visit[101010];
bool cycle[101010];
int N, M, cnt = 0;
void dfs(int s, int prev){
	visit[s] = true;
	for(int tmp : v[s]){
		if(!visit[tmp]){
			dfs(tmp, s);
		}
		else if(!cycle[tmp] && tmp != prev){
			cnt += 1;
		}
	}
	cycle[s] = true;
}
int main(){
	int ans = 0;
	scanf("%d %d", &N, &M);
	for(int i=0; i<M; i++){
		int U, V;
		scanf("%d %d", &U, &V);
		v[U].push_back(V);
		v[V].push_back(U);
	}
	for(int i=1; i<=N; i++){
		if(!visit[i]){
			dfs(i, 0);
			ans += 1;
		}
	}
	printf("%d", ans-1+cnt);
	return 0;
}