백준 20040 사이클 게임 [자바]

11 Jun 2022 in Develop / Solving

java

문제 분석

• N개의 점이 주어지고, m번 점을 연결함.
• 점을 연결하다가, 점 사이에 사이클이 생기면, 사이클이 생긴 명령의 번호를 출력.
• 사이클이 생기지 않으면 0을 출력

입력조건

점의 수 N, 차례의 수 M
M열에 걸쳐서 {
	연결 시작점 끝점
}

풀이과정

• 서로소 집합.
• 같은 부모를 가지고 있는지를 비교하다가, 부모가 같으면 바로 현재 차례를 출력하고 return
• 다 도는 동안 return되지 않으면, 0 을 출력

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ20040_사이클게임 {
	static int[] p;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		p = new int[N];
		for(int i = 0; i < N; i++) p[i] = i;

		for(int m = 1; m <= M; m++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			if(parent(a) == parent(b)) {
				System.out.println(m);
				return;
			}
			union(a, b);
		}
		System.out.print(0);
	}
	public static void union(int x, int y) {
		p[parent(y)] = parent(x);
	}
	public static int parent(int x) {
		if(p[x] == x) return x;
		else return p[x] = parent(p[x]);
	}
}