[ BOJ - 20040번 ] 사이클 게임 (C++)

https://www.acmicpc.net/problem/20040

 노드의 개수가 최대 500000, 선분의 개수가 최대 500000이므로 최대 O(n+m log n+m)인 알고리즘을 사용해야 한다.

union-find 알고리즘을 사용해 문제를 해결했다.

 

[ 정답 코드 ]

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N, M;
vector<int> parent;

int res = 1;

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

void mergeUV(int u, int v) {
    u = findParent(u);
    v = findParent(v);
    if(u == v) return;
    
    if(u < v) {
        parent[v] = u;
    } else {
        parent[u] = v;
    }
}

int main() {
    
    iostream::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M;
    parent.resize(N);
    for(int i = 0; i < N; i++) {
        parent[i] = i;
    }
    
    for(int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        
        if(findParent(u) == findParent(v)) {
            cout << res << '\n';
            return 0;
        }
        
        mergeUV(u, v);
        res++;
    }
        
    
    
    cout << 0 << '\n';
    
    return 0;
}

 

 

[ 경로 압축 ] 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N, M;
vector<int> parent;

int res = 1;

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

void mergeUV(int u, int v) {
    u = findParent(u);
    v = findParent(v);
    if(u == v) return;
    
    if(u < v) {
        parent[v] = u;
    } else {
        parent[u] = v;
    }
}

int main() {
    
    iostream::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M;
    parent.resize(N);
    for(int i = 0; i < N; i++) {
        parent[i] = i;
    }
    
    for(int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        
        if(findParent(u) == findParent(v)) {
            cout << res << '\n';
            return 0;
        }
        
        mergeUV(u, v);
        res++;
    }
        
    
    
    cout << 0 << '\n';
    
    return 0;
}

 

[ Union 최적화 ] 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N, M;
vector<int> parent;
vector<int> length;

int res = 1;

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

void mergeUV(int u, int v) {
    u = findParent(u);
    v = findParent(v);
    if(u == v) return;
    
    if(length[u] < length[v]) swap(u, v);
    if(length[u] == length[v]) length[u]++;
    parent[v] = u;
}

int main() {
    
    iostream::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M;
    parent.resize(N);
    length.resize(N);
    for(int i = 0; i < N; i++) {
        parent[i] = i;
        length[i] = 1;
    }
    
    for(int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        
        if(findParent(u) == findParent(v)) {
            cout << res << '\n';
            return 0;
        }
        
        mergeUV(u, v);
        res++;
    }
        
    cout << 0 << '\n';
    
    return 0;
}