백준 20040 C++

• 유니온 파인드(Union-Find)
  • 서로소 집합(disjoint set)을 효율적으로 다루기 위한 자료 구조
    • 서로소 집합: 서로 교집합이 없는 집합
  • Union(합집합) 연산: 두 개의 서로소 집합을 하나로 합치는 연산
  • Find(찾기) 연산: 루트 노드를 찾는 연산
  • 트리 구조를 사용하여 각 집합을 표현
  • 각 노드는 집합의 한 원소를 나타냄
  • 트리의 루트는 해당 집합을 대표하는 원소
  • 각 집합에 대한 루트 노드를 찾는 과정이 최적화되어 있으므로, 연산의 시간 복잡도를 낮출 수 있다

#include<iostream>
using namespace std;

int n, m;
int parent[500000];
int ans;

// 노드 u가 속한 집합의 대표 노드(부모)를 찾는 함수
int find(int u)
{
    if (parent[u] == u) return u;  // 자기 자신이 대표 노드인 경우
    else return parent[u] = find(parent[u]);  // 재귀: 부모 노드를 찾을 때까지 실행
}

// 두 노드를 연결하는 함수
bool union_node(int u, int v)
{
    u = find(u);
    v = find(v);

    // 부모노드가 같으면 사이클이 완성므로 true 반환
    if (u == v) return true;
    else // 노드 결합
    {
        parent[u] = v;
        return false;
    }
}

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

    int u, v;
    cin >> n >> m;

    // 자기 자신을 부모로 지정하여 초기화
    for (int i = 0; i < n; i++)
        parent[i] = i;

    // Union Find
    for (int i = 1; i <= m; i++)
    {
        cin >> u >> v;
        if (union_node(u, v))
        {
            ans = i;  // 사이클이 완성된 차례의 번호 기록
            break;
        }
    }

    if (ans == 0) cout << 0;  // 사이클이 완성되지 않은 경우 0을 출력
    else cout << ans;  // 사이클이 완성된 경우 사이클을 완성한 차례의 번호를 출력

    return 0;
}