[백준(Baekjoon)][자바(java)] 4803 : 트리 / 트리

 

www.acmicpc.net/problem/4803

4803번: 트리

 

문제 풀이

 

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

public class Main {
	
	public static int find( int x, int p[] ) {
		if( x == p[x] )	return x;
		return p[x] = find( p[x], p );
	}
	
	public static void union( int a, int b, int p[], boolean f[] ) {
		if( a == b )  return;
		a = find( a, p );
		b = find( b, p );
		if( a == b || ( !f[a] || !f[b] ) )
			f[a] = f[b] = false;
		p[b] = a;
	}
	
	public static void main(String[] args) throws IOException {
	
		StringBuilder sb = new StringBuilder();
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		StringTokenizer st;
		int n, m, a, b, c = 0, i, t, p[];  String str;
		boolean f[];  // flag -- isTree
		while( true ) {
			st = new StringTokenizer( br.readLine() );
			n = Integer.parseInt( st.nextToken() );
			m = Integer.parseInt( st.nextToken() );
			if( n == 0 && m == 0 )
				break;
			p = new int[n];
			f = new boolean[n];
			for( i = 0; i < n; i++ ) {
				p[i] = i;
				f[i] = true;
			}
			for( i = 0; i < m; i++ ) {
				st = new StringTokenizer( br.readLine() );
				a = Integer.parseInt( st.nextToken() ) - 1;
				b = Integer.parseInt( st.nextToken() ) - 1;
				union( Math.min( a, b ), Math.max( a, b ), p, f );
			}
			t = 0;
			for( i = 0; i < n; i++ ) {
				if( f[ find( i, p ) ] ) {
					f[ find( i, p ) ] = false;
					t++;
				}
			}
			if( t == 0 )		str = "No trees.";
			else if( t == 1 )	str = "There is one tree.";
			else				str = "A forest of " + t + " trees.";
			sb.append( "Case " + (++c) + ": " + str + "\n" );
		}
		br.close();
		System.out.println( sb.toString() );
	}
}

 

*  유니온 파인드

-  간선 입력받을 때 두 정점을 union() 함
   이미 같은 집합 안에 있거나 두 정점 중 하나가 트리가 아닌 경우 두 정점 모두 트리가 아님
-  boolean 타입의 flag 배열을 생성하여 정점 i가 트리가 아니면 f[i] = false  
-  f 배열을 차례로 순회하며 find() 하여 정점 i가 속한 루트노드를 구하고 트리가 맞다면 트리의 개수를 카운트 함