BOJ 20040번: 사이클 게임

문제

문제 바로가기> BOJ 20040번: 사이클 게임

20040번: 사이클 게임

 

풀이

union-find를 이용하여 cycle을 찾아주었다.

#include<iostream>
#define MAX 500005
using namespace std;

int N, M;
int par[MAX];

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

int union_(int y, int x){
    int py = find_(y);
    int px = find_(x);
    if(py != px) {
        par[px] = py;
        return 0;
    }
    return 1;
}

void solve(){
    cin >> N >> M;

    // 1. 초기화
    for (int i = 0; i < N; i++)
        par[i] = i;

    // 2. cycle 찾기
    int ans = 0;
    for (int m = 1; m <= M; m++){
        int y, x; cin >> y >> x;
        if(union_(y, x)) {
            ans = m;
            break;
        }
    }
    
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    solve();
}

 

 

처음에 아래와 같이 풀어서 "시간 초과" 가 발생했는데, 불 필요한 find_() 연산이 발생하기 때문인 것 같다.

find_(y) != find_(x) 로 확인하고, union_(y, x) 연산 안에서도 또 재귀적으로 대표 노드를 찾는 find_() 함수를 사용하니까..!

#include<iostream>
#define MAX 500005
using namespace std;

int N, M;
int par[MAX];

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

int union_(int y, int x){
    par[find_(x)] = find_(y);
}

void solve(){
    cin >> N >> M;

    // 1. 초기화
    for (int i = 0; i < N; i++)
        par[i] = i;

    // 2. cycle 찾기
    int ans = 0;
    for (int m = 1; m <= M; m++){
        int y, x; cin >> y >> x;

        if(find_(y) != find_(x)) {
            union_(y, x);
        }
        else{
            ans = m;
            break;
        }
    }
    
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    // freopen("../test/input.txt", "r", stdin);
    solve();
}