경우없는 개발 블로그

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

#문제 간단 정리

사이클이 언제 생성되는지 출력하는 문제

즉 사이클을 확인할 수 있는 유니온 파인드 (Union-Find)를 알고 있는지 물어보는 문제다

그렇기 때문에 유니온 파인드를 구현하자

#문제 해결 방법

유니온 파인드 동작 방식

유니온 파인드에서는 각 노드가 하나의 그룹을 나타내고, 각 그룹은 트리 구조로 구성됩니다. 트리의 루트 노드는 그 그룹을 대표합니다. 초기 상태에서는 각 노드가 자기 자신만을 포함하는 독립적인 그룹을 형성합니다.

1. Find 연산: 특정 노드가 속한 그룹의 대표(루트 노드)를 찾습니다. 노드가 속한 트리의 루트 노드를 찾아 그룹을 식별할 수 있습니다.
2. Union 연산: 두 개의 노드가 주어졌을 때, 이 노드들을 포함하는 두 그룹을 하나로 합칩니다. 이는 두 트리의 루트 노드를 연결하여 수행됩니다.

사이클 게임 문제 해결 방법

사이클 게임에서는 점들이 주어지고, 차례대로 점들을 연결하는 선분을 그립니다. 사이클이 형성되는 순간 게임이 종료됩니다. 사이클이란, 선분들이 연결되어 처음 시작한 점으로 돌아올 수 있는 경로를 의미합니다.

문제를 풀 때 유니온 파인드를 사용하는 이유는 각 선분을 그릴 때마다 두 점이 이미 같은 그룹에 속해 있는지(Find)를 확인하고, 속하지 않는 경우 두 점을 연결하는 그룹을 하나로 합치기(Union) 위함입니다.

1. 초기 상태: 모든 점은 자기 자신만을 포함하는 독립적인 그룹을 형성합니다.
2. 선분을 그릴 때마다: 주어진 두 점에 대해 Find 연산을 수행하여, 두 점이 이미 같은 그룹에 속해 있는지 확인합니다.
   • 같은 그룹에 속해 있지 않다면: 이는 아직 사이클이 형성되지 않았음을 의미합니다. 이 경우, 두 점을 연결하는 Union 연산을 수행하여 두 그룹을 합칩니다.
   • 같은 그룹에 속해 있다면: 두 점을 연결하는 순간 사이큀이 형성됩니다. 왜냐하면 이미 같은 그룹에 속해 있다는 것은 이전에 이 두 점을 경유하는 경로가 이미 존재한다는 것을 의미하며, 두 점을 다시 연결하면 사이클이 완성되기 때문입니다.
3. 사이클 형성 여부: 만약 같은 그룹에 속해 있다는 것이 확인되면, 그 순간이 바로 사이클이 처음으로 형성된 차례입니다.

#전체 코드

#include <iostream>
#include <vector>
using namespace std;

#define MAX 500000

int parent[MAX]; // 부모 노드를 저장하는 배열

int Find(int x) {
    if (parent[x] == x)
        return x;
    return parent[x] = Find(parent[x]); // 경로 압축
}

void Union(int x, int y) { // 함수 이름을 `Union`으로 변경
    x = Find(x);
    y = Find(y);

    if (x != y) {
        if (x < y)
            parent[y] = x;
        else
            parent[x] = y;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    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 (Find(a) == Find(b)) {
            cout << i; // 사이클이 처음으로 만들어진 차례의 번호 출력
            return 0;
        }

        Union(a, b); // 두 노드를 하나의 집합으로 합치기
    }

    cout << "0"; // 모든 차례를 처리한 후에도 사이클이 형성되지 않았다면 0 출력
    return 0;
}