[백준 4803] 트리 (Java)

문제 링크: www.acmicpc.net/problem/4803

4803번: 트리

1. 주의할 점

- 모든 TC가 진행되기 전, 변수를 초기화한다

- 트리가 이뤄지지 않은 Node는 무시한다 → 무조건 Tree가 없다고 하면 WA

 

2. 구현

- 트리의 특징인 노드 N개 → 간선 N-1개를 통해 MST를 떠올린다(MST도 똑같이 노드 N개, 간선 N-1개)

- 트리가 많을 수 있기 때문에 MST의 방법중 하나인 유니온 파인드를 사용한다

- Par[] 함수를 통해 각 Node의 부모(속한 트리의 번호)를 저장한다

- finP() 함수를 통해 각 Node가 속한 Tree의 번호를 갱신 및 반환한다

- Make_union(a,b) 함수를 통해 Node A와 B를 연결 시도한다. 이미 같은 트리인 경우, 각 부모를 0으로 초기화한다

- 모든 간선에 대한 정보를 다 입력받았으면 HashSet을 통해 트리의 총 개수를 구해서 이에 해당하는 문구를 출력한다

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

public class Main {
    static int node,edge;
    static int par[];
    static HashSet<Integer> hs;
    
    static int findP(int x){
        if(par[x]==x) return x;
        return par[x] = findP(par[x]);
    }
    
    static void make_union(int a,int b){
        int pa = findP(a);
        int pb = findP(b);
        if(pa==pb){     //이미 같은 트리
            par[pb] = pa;
            par[pa] = 0;
        }
        else if(pa<pb) par[pb] = pa;
        else par[pa] = pb;
    }
    
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    int a,b,test=1;
	    while(true){
	        String ss = br.readLine();
    	    StringTokenizer st = new StringTokenizer(ss);
    	    node = Integer.parseInt(st.nextToken());
    	    edge = Integer.parseInt(st.nextToken());
    	    if(node==0 && edge==0) break;
    	    
    	    //초기화
    	    par = new int[node+1];
    	    for(int i=1;i<=node;i++)
    	        par[i]=i;   	    
    	    hs = new HashSet<>();
    	    
    	    for(int i=0;i<edge;i++){
    	        ss = br.readLine();
    	        st = new StringTokenizer(ss);
    	        a = Integer.parseInt(st.nextToken());
    	        b = Integer.parseInt(st.nextToken());
    	        make_union(a,b);
    	    }
    	    for(int i=1;i<=node;i++){
    	        int pi = findP(i);
    	        if(pi>0)
    	            hs.add(pi);
    	    }
    	    if(hs.isEmpty())
    	        System.out.println("Case "+test+": No trees.");
    	    else if(hs.size()==1)
    	        System.out.println("Case "+test+": There is one tree.");
    	    else
    	        System.out.println("Case "+test+": A forest of "+hs.size()+" trees.");
    	    test++;
	    }
	}
}