[BAE/<JOON> 문제풀이] 20040. 사이클 게임

www.acmicpc.net/problem/20040

20040번: 사이클 게임

 

간선이 추가 될 때마다 부모를 추적하고 같은 부모를 가진다면 해당 간선번호를 출력한다.

 

#include <iostream>
#include <vector>

using namespace std;

int parent[500001];

int findp(int x) {
	if (parent[x] == x) return x;
	return parent[x] = findp(parent[x]);
}

struct node {
	int s, e;
};

int main()
{
	int n, m;
	cin >> n >> m;
	vector<node> arr(m + 1);

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

	for (int i = 1; i <= m; i++) {
		cin >> arr[i].s >> arr[i].e;
	}

	for (int i = 1; i <= m; i++) {
		int p1 = findp(arr[i].s);
		int p2 = findp(arr[i].e);
		if (p1 != p2) {
			parent[p2] = p1;
		}
		else {
			cout << i;
			return 0;
		}
	}

	cout << 0;
	return 0;
}