백준 - 20955번 : 민서의 응급 수술(C++)

풀이 방법 : 분리 집합

연결을 끊거나 연결하거나, 두 가지 연산으로 트리 형태의 그래프를 만들어야 한다.
입력으로 이미 연결되어 있는 뉴런이 주어진다고 했다.

만약 입력으로 들어온 뉴런들을 연결하면 사이클이 발생하는 경우 이것은 연결되면 안된다.
즉, 연결을 끊는 연산이 필요하다는 것이다.

유니온 파인드를 통해 입력으로 주어진 뉴런들을 다 처리한 뒤 각각의 트리끼리 연결시켜주면 된다. 이 횟수는 부모노드의 갯수로 파악할 수 있다. 만약 부모 노드가 N개라면 따로따로 존재하는 트리 또한 N개라는 것이므로 N-1번의 연결과정을 통해 이를 모두 통합해줄 수 있다.

#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>

using namespace std;

int Root[100001] = {};
bool Check[100001] = { };

int Find(int Num)
{
	if (Root[Num] == Num)
	{
		return Root[Num];
	}

	Root[Num] = Find(Root[Num]);
	return Root[Num];
}

bool Union(int Src, int Dest)
{
	int SrcParent = Find(Src);
	int DestParent = Find(Dest);

	if (SrcParent != DestParent)
	{
		Root[DestParent] = SrcParent;
		return true;
	}

	return false;
}

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;

	for (int i = 1; i <= N; ++i)
		Root[i] = i;

	int Cnt = 0;
	for (int i = 0; i < M; ++i)
	{
		int Src, Dest;
		cin >> Src >> Dest;
		if (!Union(Src, Dest))
			++Cnt;
	}

	for (int i = 1; i <= N; ++i)
	{
		int Root = Find(i);

		if (Check[Root])
			continue;

		Check[Root] = true;
		++Cnt;
	}

	cout << Cnt - 1;
}