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

문제 링크

https://www.acmicpc.net/problem/20955

20955번: 민서의 응급 수술

 

문제

민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서는 놀라 자빠질 수밖에 없었다. 한 학생이 꾸벅꾸벅 졸다가 책상에 머리를 아주 세게 박았기 때문이다. 한시라도 수술이 시급한 상황, 민서는 의사가 되어 수술을 집도하기로 결심하였다.

사람의 뇌는 수백억 개의 뉴런으로 구성되며, 각 뉴런은 시냅스를 통하여 연결된다. 민서의 진찰 결과, 학생은 뇌 속의 일부 뉴런의 연결이 끊어져 잠이 든 것으로 확인되었다. 끊어진 시냅스만 복구된다면 학생은 잠에서 깨어나겠지만, 알다시피 민서는 컴퓨터공학과 교수이다.

민서는 끊어진 시냅스를 복구하는 대신 뇌 속의 모든 뉴런을 하나의 트리 형태로 연결해보고자 한다. 여기서 트리란 사이클이 존재하지 않는 연결 그래프를 의미한다.

민서는 손기술이 뛰어나기 때문에 다음과 같은 연산을 무한히 수행할 수 있다. 연결되지 않은 두 뉴런을 연결하거나 이미 연결된 두 뉴런의 연결을 끊는다.

뉴런의 연결 정보가 주어졌을 때, 모든 뉴런을 하나의 트리 형태로 연결하기 위하여 필요한 최소 연산 횟수를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 뉴런의 개수 N과 시냅스의 개수 M이 주어진다.

이후 M개의 줄에 걸쳐 시냅스로 연결된 두 뉴런의 번호 u, v가 주어진다.

모든 입력은 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 모든 뉴런을 트리 형태로 연결하기 위하여 필요한 최소 연산 횟수를 출력한다.

제한

• 2 ≤ N ≤ 100,000
• 1 ≤ M ≤ min(N × (N – 1) / 2, 100,000)
• 1 ≤ u, v ≤ N
• u ≠ v
• 두 뉴런 사이에는 최대 1개의 시냅스만 존재한다.

예제 입력 1

4 2
1 2
3 4

예제 출력 1

1

알고리즘 분류

• 유니온 파인드

풀이

아직 모든 뉴런이 연결되어 있지 않은 상태이기 때문에, 시냅스가 주어질 때마다 뉴런을 연결하고, 사이클이 존재하는 그래프가 아닌, 사이클이 없는 트리 형태로 뉴런들을 연결하고 싶기 때문에, 이미 연결되어 있는 뉴런들이라면 연결을 끊는다.(즉 연결을 끊을 횟수를 1 증가시킨다.)

모든 시냅스의 정보를 처리했다면, N개의 뉴런을 검사해서 그룹의 개수를 조사한다.(즉 Parent가 자기 자신인 뉴런들의 개수를 조사한다.) 그룹을 다 연결하면 되는 것이므로, 필요한 연결 횟수는 그룹의 개수-1이 된다.

따라서, 민서가 해야 할 연산 횟수는 (뉴런 그룹의 개수)-1+(주어진 시냅스 중 이미 연결되어 있는 뉴런들인 시냅스의 개수)이다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100001
#define LL long long
#define INF 1e9

using namespace std;
int N, M;
int Parent[MAX];
int answer = 0;
int Cycle = 0;

void Init() {
	for (int i = 0; i < MAX; i++) {
		Parent[i] = i;
	}
}

int Find(int X) {
	if (Parent[X] == X) {
		return X;
	}
	return Parent[X] = Find(Parent[X]);
}

void Union_Group(int X, int Y) {
	int P_X = Find(X);
	int P_Y = Find(Y);
	if (P_X != P_Y) {
		Parent[P_Y] = P_X;
	}
}

void Input() {
	Init();
	scanf_s("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		int U, V;
		scanf_s("%d %d", &U, &V);
		if (Find(U) != Find(V)) {
			Union_Group(U, V);
		}
		else {
			Cycle++;
		}
	}
}

void Find_Answer() {
	for (int i = 1; i <= N; i++) {
		if (Find(i) == i) {
			answer++;
		}
	}
	printf("%d\n", answer - 1 + Cycle);
}

int main() {
	FASTIO
	Input();
	Find_Answer();

	return 0;
}