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

문제 링크: https://www.acmicpc.net/problem/20040

20040번: 사이클 게임

1. 주의할 점

- 분리집합 알고리즘에 대해 알고 있어야 한다

 

2. 구현

- findPar() 함수를 통해 해당 Node의 부모를 반환하는 함수를 구현한다

- makeUnion() 함수를 통해 a와 b의 최상위 부모를 연결한다

- M개의 선분을 입력받으면서 해당 선분의 부모가 같지 않으면 makeUnion()을 통해 같게 해준다. 만약 같고 finish 값이 0이 아니라면 finish의 값을 갱신한다

#include <iostream>
using namespace std;
int node,edge,from,to;
int par[500000];

int findPar(int x){
    if(par[x]==x) return x;
    return par[x] = findPar(par[x]);
}

void makeUnion(int a, int b){
    int pa = findPar(a);
    int pb = findPar(b);
    if(pa<pb) par[pb]=pa;
    else if(pa>pb) par[pa]=pb;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>>node>>edge;
    int finish=0;
    for(int i=0;i<node;i++)
        par[i]=i;
    for(int i=1;i<=edge;i++){
        cin>>from>>to;
        if(finish!=0) continue;
        int pf = findPar(from);
        int pt = findPar(to);
        if(pf!=pt)  makeUnion(from,to);
        else finish=i;
    }
    cout<<finish;
    return 0;
}