[백준 20040/] 사이클게임 java

문제

 

Union-find 를 활용하는 기본적인문제이다. 

선택한 두 점의 번호를 한 집합으로 합쳐가는데, 이 때 두 번호가 모두 이미 선택된(집합에 이미 속한)번호들이라면 사이클이 생긴다.

사이클이 발생하면 이후의 입력값들은 더이상 볼 필요 없이 바로 종료하면 된다.

 

Java 코드

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

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());
		
		
		init(); // 부모정보를 담을 배열 초기화 
		
		boolean isCycle = false; //사이클 있는지 체크할 변수 
		int seq = 0;
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			if(!union(from,to)) { // 두 점이 합쳐지지 않은 경우 => 이미 두 점이 집합에 포함된경우
				isCycle = true; 
				seq = i+1;
				break; // 사이클이 발생했으므로 바로 반복문 종료 
			}
		}
		if(isCycle) {
			System.out.println(seq); //사이클이 있다면 사이클이 생긴 순서 출력 
		}else {
			System.out.println(0); //사이클이 없다면 0 출력 
		}
		
	}

	private static boolean union(int u, int v) { // 두 점을 집합에 포함시키는 함수 
		int uParent = find(u); 
		int vParent = find(v);
		if(uParent==vParent) return false; // 두 점의 부모가 같다면 이미 집합에 포함된 점들.
		parent[vParent]=uParent; // 집합에 합치기 
		return true;
	}

	private static int find(int u) { // 점의 부모 번호를 찾는 함수
		if(parent[u]==u) return u;
		return parent[u]=find(parent[u]);
	}

	private static void init() { // 초기화 
		parent = new int[N];
		for(int i=0;i<N;i++)
			parent[i]=i;
	}
	
	
	
	

}