[백준 C++] 20040 사이클 게임 - 분리집합

20040번: 사이클 게임

#include <iostream>
using namespace std;

int Root[500000];

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

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

bool Cycle(int NodeA, int NodeB)
{
	int RootA = Find(NodeA);
	int RootB = Find(NodeB);

	if (RootA == RootB)
	{
		return true;
	}

	// Union
	int NewRoot = min(RootA, RootB);
	Root[RootA] = NewRoot;
	Root[RootB] = NewRoot;

	return false;
}

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

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

	for (int i = 0; i < N; ++i)
	{
		Root[i] = i;
	}

	bool bFound = false;
	int Cnt = 0;
	for (int i = 1; i <= M; ++i)
	{
		int A, B;
		cin >> A >> B;

		if (!bFound && Cycle(A, B))
		{
			bFound = true;
			Cnt = i;
		}
	}

	cout << Cnt;
}

---

 

일반적인 분리 집합 유형의 문제입니다.

유니온 연산을 입력했을 때 두 노드의 루트 노드가 같다면 사이클이 만들어지게 됩니다.

따라서 사이클이 처음 만들어지는 해당 차례를 출력해주면 됩니다.