Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

29. 유니온 파인드

유니온 파인드(또는 disjoint set, 상호 배타적 집합, ...) 자료구조를 배워 봅시다.

Java / Python

4. 사이클 게임

20040번

간선을 점차 추가하면서 사이클을 찾는 문제

이번 문제는 입력으로 점의 개수 n과 m 번째 차례까지의 게임 진행 상황이 주어지면 사이클이 완성 되었는지를 판단하고, 완성되었다면 몇 번째 차례에서 처음으로 사이클이 완성된 것인지를 출력하는 문제이다.

parent를 자기 자신으로 초기화하고, 부모를 찾는 함수 find와 합집합 연산을 해, 같은 부모를 가지도록 하는 union함수를 이용한다.

• Java

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

public class Main {
	static int[] parent;
	static int N, M, result;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		int N = Integer.parseInt(st.nextToken());
		int 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 (!union(a, b)) {
				result = i;
				break;
			}
		}
		bw.write(result + "\n");
		bw.flush();
		bw.close();
		br.close();
	}

	// x의 부모 찾기
	public static int find(int x) {
		if (x == parent[x])
			return x;

		return parent[x] = find(parent[x]);
	}

	// y 부모를 x 부모로 치환하기 
	public static boolean union(int x, int y) {
		x = find(x);
		y = find(y);

		if (x == y)
			return false;
		parent[y] = x;
		return true;
	}
}

• Python

파이썬에 있는 문법인 for-else문에서 else는 for문이 중간에 break 등으로 끊기지 않고, 끝까지 수행 되었을 때 수행하는 코드를 담고 있다.

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def find(x):
    if x == parent[x]:
        return x
    parent[x] = find(parent[x]) # 부모 테이블 갱신
    return parent[x]

def union(x,y):
    x = find(x)
    y = find(y)

    if x > y:
        parent[x] = y
    else :
        parent[y] = x

N, M = map(int, input().split())
parent = [i for i in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    if find(a) == find(b):
        print(i+1)
        break
    union(a, b)
else :
    print(0)