[백준] 20040번 : 사이클 게임

문제

 

---

풀이

 

myunji.tistory.com/350

[백준] 4803번 : 트리

이 문제에서 사이클을 찾는 코드를 작성하긴 했었다.

 

근데 이번 문제는 사이클이 생기는 지점을 정확히 찾아야 하기도 하고...해서 유니온 파인드로 풀 것이다.

달리말하면 4803번도 유니온 파인드로 풀 수 있단 뜻이다.

 

아무튼 유니온 파인드에서 사이클이 형성된다는 것을 알 수 있는 기점은

유니온 하려는 x와 y의 부모가 같을 때이다.

---

소스코드

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> parent;

int findParent(int x) { //parent[x]가 음수가 될 때까지(root에 다다를 때까지) 재귀 함수 호출
    if (parent[x] < 0)
        return x;
    return parent[x] = findParent(parent[x]);
}

bool unionInput(int x, int y) { //부모가 같으면 cycle 이라는 것
    int x_p = findParent(x); //x의 부모
    int y_p = findParent(y); //y의 부모

    if (x_p == y_p) //이미 같은 집합
        return true;
    if (parent[x_p] < parent[y_p]) { //x_p를 root로 하는 노드가 더 많으면 x_p -> y_p
        parent[x_p] += parent[y_p];
        parent[y_p] = x_p;
    } else { //y_p를 root로 하는 노드가 더 많으면 y_p -> x_p
        parent[y_p] += parent[x_p];
        parent[x_p] = y_p;
    }
    return false;
}

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

    int n, m, x, y;

    cin >> n >> m;
    parent.assign(n, -1);
    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        bool is_cycle = unionInput(x, y);
        if (is_cycle) { //사이클이 형성됨 = x와 y의 부모가 같음
            cout << i + 1;
            return 0;
        }
    }
    cout << 0;
}

전체 소스코드다.

 

    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        bool is_cycle = unionInput(x, y);
        if (is_cycle) { //사이클이 형성됨 = x와 y의 부모가 같음
            cout << i + 1;
            return 0;
        }
    }
    cout << 0;

이번엔 유니온 함수가 bool 값을 리턴할 건데 만약 이 값이 true라면 사이클이 생겼다는 뜻이다.

그럼 즉시 해당 인덱스 (i+1)을 리턴하고 반복문을 다 도는 동안 그럴 일이 없었다면 사이클이 없단거니 0을 리턴한다.

 

bool unionInput(int x, int y) { //부모가 같으면 cycle 이라는 것
    int x_p = findParent(x); //x의 부모
    int y_p = findParent(y); //y의 부모

    if (x_p == y_p) //이미 같은 집합
        return true;
    if (parent[x_p] < parent[y_p]) { //x_p를 root로 하는 노드가 더 많으면 x_p -> y_p
        parent[x_p] += parent[y_p];
        parent[y_p] = x_p;
    } else { //y_p를 root로 하는 노드가 더 많으면 y_p -> x_p
        parent[y_p] += parent[x_p];
        parent[x_p] = y_p;
    }
    return false;
}

그냥 이미 같은 집합이면 true를 반환하고

그렇지 않아서 유니온 연산을 했다면 false를 반환했다.