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

문제 - 사이클 게임 (Gold4)

[백준 20040] https://www.acmicpc.net/problem/20040

풀이 전략

DisjointSet을 이용하는 문제이다. Union-Find 알고리즘을 이용하여 두 노드가 같은 집합에 있는지 확인하고 다른 집합에 있으면 합쳐주는 방식으로 집합을 구성한다. 그런데 이 문제의 경우 입력받은 모든 노드쌍을 같은 집합으로 만든 뒤, 사이클 생성 여부를 확인하는 문제이므로 Union을 하면서 isCycle 함수로 사이클 여부를 확인한 뒤 isCycle==true인 경우 그 때 입력받은 순서를 출력하면 된다.

풀이

그림으로 그려보면 예제 1, 2가 위의 그림과 같다. 예제 1의 경우 cycle이 생성되지 않았기 때문에 0을 출력하면 되고, 예제 2의 경우 0-1, 1-2, 1-3, 0-3, 4-5 이 순서대로 입력을 받는데 4번째로 입력받은0-3이 입력되었을 때 Cycle이 생성되기 때문에 4를 출력한다. 본인의 경우, 순서를 vector에 pair<pair<int, int>, int>로 ({{시작 노드, 도착 노드}, 순서}) 순으로 저장을 해서 cycle인 경우 edge.second를 출력하도록 했다.
약간 Dijkstra algorithm에서 vertex와 edge의 정보를 입력 받아서 vertex 사이의 거리 edge를 더해가는 것 처럼 edge에 거리 대신에 입력받은 순서를 저장한 셈이라고 보면 된다.

소스 코드

/*
# Question: BJ 20040 (https://www.acmicpc.net/problem/20040)
# Rank: Gold4
# Algorithm: Data Structure, DisjointSet
*/

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX 1000000
using namespace std;
typedef pair<pair<int, int>,int> piii;

int N, M;
int parent[MAX];
vector<piii> edges;

void Input() {
    cin>>N>>M;
    for(int i=1; i<=M; i++){
        int a, b;
        cin>>a>>b;
        edges.push_back({{a, b}, i}); // ({{시작 노드, 도착 노드}, 순서})
    }

    for(int i=0; i<N; i++) // Parent를 초기화
        parent[i] = i;
}

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

void Union(int x, int y){
    x = Find(x);
    y = Find(y);

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

bool isCycle(int x, int y){
    x = Find(x);
    y = Find(y);

    if(x == y)
        return true;
    return false;
}

int main() {
    fastio
    Input();
    
    for(int i=0; i<edges.size(); i++){
        int a = edges[i].first.first;
        int b = edges[i].first.second;

        if(isCycle(a, b)){ // 사이클이 생성된 경우 순서를 출력한 뒤 프로그램 종료
            cout<<edges[i].second<<"\n";
            return 0;
        }
        Union(a, b);
    }
    cout<<0<<"\n"; // 끝까지 사이클이 생성되지 않은 경우 0 출력
    return 0;
}

결과