[골4] 20040 - 사이클 게임

모든 입력을 받을 필요가 없다.

 

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

using namespace std;
using ll = long long;

#pragma region 상하좌우 / 위치

const pair<int, int> dir[]
{
	{  1,  0 },
	{ -1,  0 },
	{  0, -1 },
	{  0,  1 },
};

#define y first
#define x second

#pragma endregion

#pragma region 빠른 입출력

#define FAST_IO() \
{\
	ios::sync_with_stdio(false);\
	cin.tie(NULL); \
	cout.tie(NULL); \
}\

#pragma endregion

#define MAX 500000

int parent[MAX];

int Find(int a)
{
	if (parent[a] == a)
		return a;

	else
		return parent[a] = Find(parent[a]);
}

void Union(int a, int b)
{
	a = Find(a), b = Find(b);
	parent[a] = b;
}

bool IsCycle(int a, int b)
{
	return Find(a) == Find(b);
}

int main()
{
	FAST_IO();

	int n, m, ans = 0;
	cin >> n >> m;


	for (int i = 1; i < n; i++)
		parent[i] = i;

	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;

		if (IsCycle(a, b))
		{
			cout << i + 1;
			return 0;
		}
		Union(a, b);
	}
	cout << ans;
	return 0;
}