[백준/C++] 20040번 사이클 게임

백준

---

🤔문제 이해

선분을 긋다가 사이클이 발생하는 지점을 찾는 문제이다. 점의 위치를 정확히 몰라도 선분으로 이어져있는 경우를 찾으면 된다.

---

🔥풀이🔥

Find-Union 문제로 두 점을 이어줄 때마다 그 점들의 집합의 번호를 갱신해준다. 

그러다가 어떤 두 점을 이을 때 한 점의 집합과 다른 한 점의 집합의 번호가 같다는 것은 이미 어떠한 경로로 연결되어 있는 상태에서 또 선분을 그어주는 것 즉, 사이클이 생기는 것이므로 그 때의 차례 번호를 ans 변수에 저장해둔다. 

m번까지의 차례는 모두 입력받아야 하기 때문에 flag를 통해 ans를 구한 경우엔 두 점을 입력받기만 하고 이외의 연산은 하지 않는다.

마지막으로 ans를 출력해주면 된다.

 

---

#include <iostream>

using namespace std;

int n, m, x, y;
int par[500002];
int ans;

int Find(int a) {
    if (par[a] == a)
        return a;

    return par[a] = Find(par[a]);
}

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

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        par[i] = i;
    }
    int flag = 1;
    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        if (flag) {
            int par_x = Find(x);
            int par_y = Find(y);
            if (par_x == par_y) {
                ans = i + 1;
                flag = 0;
            } else {
                par[par_y] = par_x;
            }
        }
    }
    cout << ans;
}