[백준 20040] 사이클 게임

각 간선들이 주어졌을때 사이클을 만드는 간선을 구하는 문제이다.

 

이미 간선들이 다 놓인 상태에서 사이클의 유무를 파악하는 문제라면 unoin find로 풀면 안되지만

이건 순차적으로 놓는 과정에서 사이클 유무를 판별하는 것이기 때문에

간선을 추가하기 전에 같은 집합 내 존재하는 노드들인지를 구해줌으로써

현재 놓여지는 간선이 같은 집합 내 사이클을 생성하는 간선인지 파악할 수 있다.

 

---

#include <iostream>
#include <vector>

#define SIZE 500001

using namespace std;

int N, M;

int parent[SIZE];
vector<pair<int, int>> v;

int findParent(int x)
{
    if (x == parent[x])
    {
        return x;
    }

    return parent[x] = findParent(parent[x]);
}

void updateParent(int x, int y)
{
    x = findParent(x);
    y = findParent(y);

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

bool isSameParent(int x, int y)
{
    x = findParent(x);
    y = findParent(y);

    return x == y;
}

void solve()
{
    // parent 초기화
    for (int i = 0; i < N; i++)
    {
        parent[i] = i;
    }

    for (int i = 0; i < v.size(); i++)
    {
        auto [start, end] = v[i];

        if (isSameParent(start, end))
        {
            cout << i + 1;
            return;
        }

        updateParent(start, end);
    }

    cout << 0;
    return;
}

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

    cin >> N >> M;

    int start, end;
    for (int i = 0; i < M; i++)
    {
        cin >> start >> end;
        v.push_back(make_pair(start, end));
    }

    solve();

    return 0;
}