[백준] 20040 사이클 게임 python C++

https://www.acmicpc.net/problem/20040

20040번: 사이클 게임

2월의 첫문제는 union find 문제이다. 

union에서 같은 부모를 연결하게 될 떄 cycle이 된다. 이를 사용하면 cycle 체크와 union을 같이 진행할수 있다.

# import sys; input = sys.stdin.readline
def find(a, parent):
    if parent[a] == a:
        return a
    parent[a] = find(parent[a], parent)
    return parent[a]


def union(a, b, parent):
    x = find(a, parent)
    y = find(b, parent)
    if x == y:
        return True
    parent[y] = x
    return False


def main():
    N, M = map(int, input().split())
    parent = [i for i in range(N)]
    for i in range(1, M + 1):
        u, v = map(int, input().split())
        if union(u, v, parent):
            print(i)
            return
    print("0")


if __name__ == '__main__':
    main()

#include<iostream>
using namespace std;
int p[500000];

int find(int a) {
	if (p[a] == a)
		return a;
	return p[a] = find(p[a]);
}

int cycle_check_or_union(int a, int b) {
	a = find(a);	b = find(b);
	// cycle_check
	if (a == b)
		return 1;
	// union
	p[b] = a;
	return 0;
}

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

	int N, M, i, j, u, v;
	cin >> N >> M;
	for (i = 0; i < N; i++) {
		p[i] = i;
	}
	for (i = 0; i < M; i++) {
		cin >> u >> v;
		if (cycle_check_or_union(u, v)) {
			cout << i + 1 << '\n';
			return 0;
		}
	}
	cout << "0\n";

	return 0;
}