문제 간략 설명

두 명의 플레이어가 차례대로 점을 연결하는 선분을 그으며 게임을 진행한다. 이전에 그린 선분을 다시 그을 수는 없지만 이미 그린 다른 선분과 교차하는 것은 가능하다. 게임을 진행하다가 처음으로 사이클을 완성하는 순간 게임이 종료된다. m번째 차례까지 게임을 진행한 상황에서 이미 게임이 종료되었다면 사이클이 처음으로 만들어진 차례의 번호를 출력하고, m번의 차례를 모두 처리한 이후에도 종료되지 않았다면 0을 출력한다.

풀이 방법

Union-find를 사용한다. 초기에 모든 node의 root를 자신으로 설정한다. 입력으로 들어온 간선에 대해서 서로 root가 다르면 root를 통일한다. 입력으로 root가 같으면 cycle 판단하고, 현재 단계를 저장하고 출력한다.

코드

#include <iostream>
#include <vector>

using namespace std;

int N, M;
int id = 0;
int res = 0;

vector<int> nodes;

int find(int n) 
{
	if (nodes[n] != n)
		nodes[n] = find(nodes[n]);
	return nodes[n];
}

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

	cin >> N >> M;

	for (int i = 0; i < N; i++)
		nodes.push_back(i);

	for (int i = 0; i < M; i++) {
		int n1, n2;

		cin >> n1 >> n2;

		if (res != 0)
			continue;

		int r1 = find(n1);
		int r2 = find(n2);

		if (r1 == r2)
			res = i + 1;
		else
			nodes[r1] = r2;
	}
	
	cout << res << endl;

	return 0;
}

Key Points

notepad