백준 20040 (C++) 사이클 게임

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

20040번: 사이클 게임

 

 

 

 

 

 

아이디어

분리집합을 알면 날먹 가능한 문제

이 유형이 대체로 티어가 높게 잡혀 날먹하기 좋다

 

 

입력받는 두 노드를 merge하기 전 사이클이 생기는지 확인한다.

사이클이 생긴다면 그대로 그때의 iteration(<= m, m보다 작음)값을 출력한다.

사이클이 생기지 않아 반복문을 종료하여 빠져나왔다면 "0"을 출력한다

 

 

 

 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
using ll = long long;
const int INF = 1e8;
const int MAX = 500003;
int n,m;
int Parent[MAX];
int getParent(int n1) {
    if (Parent[n1] == n1) return n1;
    else return Parent[n1] = getParent(Parent[n1]);
}
void unionParent(int n1, int n2) {
    n1 = getParent(n1);
    n2 = getParent(n2);
    if (n1 != n2) {
        Parent[n2] = n1;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    
    for (int i = 0; i < n; i++) {
        Parent[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        if (getParent(a) == getParent(b)) {
            cout << i;
            return 0;
        }
        unionParent(a, b);
    }
    cout << "0";
    return 0;
}