[백준/Baekjoon] 20040 사이클 게임 C++ & Java :: Union-find

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

20040번: 사이클 게임

---

1. Logic

유니온 파인드를 사용해서 입력받은 노드를 연결해준다. merge를 하게되면 서로의 root노드가 정해진다. 이 root노드가 같은 것 끼리 연결하게 되면 사이클이 생긴다. 즉 merge하기 전 부모 노드를 찾고 이후에 서로의 루트 노드가 같으면 사이클이 있기 때문에 출력해주고 루트 노드가 다르면 merge 해준다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n, m;

int parent[500001];

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

bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    
    if(x == y) return true;
    else {
        if(x < y) parent[y] = x;
        else parent[x] = y;
    }
    
    return false;
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    
    for(int i = 0; i < n; i++) {
        parent[i] = i;
    }
    
    for(int i = 1; i <= m; i++) {
        int s, e;
        cin >> s >> e;
        
        if(merge(s, e)) {
            cout << i;
            return 0;
        }
    }
    
    cout << 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    static int n, m;
    static int [] parent;
        
	public static void main(String[] args) throws Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
        parent = new int[n];
        
        for(int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        for(int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            if(merge(a, b)) {
                System.out.println(i);
                return;
            }
        }
        System.out.println(0);
	}
        
        static boolean merge(int x, int y) {
            x = find(x);
            y = find(y);
            
            if(x == y) return true;
            
            if(x < y) parent[y] = x;
            else parent[x] = y;
            
            return false;
        }
        
        static int find(int x) {
            if(parent[x] == x) return x;
            return parent[x] = find(parent[x]);
        }
	
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90