취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 17131번 문제인 여우가 정보섬에 올라온 이유이다.
문제는 아래 링크를 확인하자.

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

문제의 설명이 기하문제처럼 복잡하게 서술되어 있지만, 결국 구해야하는 것은 간선을 추가하다가 사이클이 생기는 때, 즉 주어지는 두 점이 속한 트리를 disjoint set 자료구조로 하나로 합쳐나가다가 같은 트리 내에 있는 두 점 사이를 이으려는 시도를 하려는 시점을 찾는 것이다. 크루스칼 알고리즘에서 추가하지 않는 간선의 조건이 무엇이었는지를 생각해보자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int arr[500000];

int findf(int x) {
    if (x == arr[x]) return x;
    return arr[x] = findf(arr[x]);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M; cin >> N >> M;
    
    for (int i = 0; i < N; i++) {
        arr[i] = i;
    }

    for (int i = 1; i <= M;i++) {
        int x, y; cin >> x >> y;
        x = findf(x), y = findf(y);
        if (x == y) {
            cout << i;
            return 0;
        }

        arr[y] = x;
    }

    cout << 0;
}