[백준] 4803번 트리 (gold 4

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

public class Main{
    static int[] num;
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int t=0;
        while(true){
            t++;
            st=new StringTokenizer(br.readLine());
            int n=Integer.valueOf(st.nextToken());
            int m=Integer.valueOf(st.nextToken());
            if(n+m==0){
                break;
            }

            num=new int[n+1];
            for(int i=1; i<=n; i++){
                num[i]=i;
            }
            boolean[] multy=new boolean[n+1];
            for(int i=0; i<m; i++){
                st=new StringTokenizer(br.readLine());
                int a=Integer.valueOf(st.nextToken());
                int b=Integer.valueOf(st.nextToken());
				
                int fa=Find(a);
                int fb=Find(b);
				//트리에서 서로 같은 부모의 트리가 합쳐지는 경우 즉 사이클이 처음 생기는 경우
                //트리에서 사이클이 있는 정점과 연결되는 경우,
                //두 정점을 모두 체크한다.
                //두 개를 모두 체크하는 이유는, 만약에 union find로 a정점이 대표 수가 되고,
                //체크된 상태가 있다고 가정하자. 근데 b정점을 a정점이랑 연결하는 과정에서 b가 대표수가
                //되어버리고, 밑에서 multy배열을 돌면서 사이클 여부를 체크할 때, b가 a보다 작은 수면
                //b는 그대로 자기 대표수를 b로 출력을 하므로 사이클 체크가 되지 않는다.
                //즉 b와 a가 합쳐진 그래프는 트리가 될 수없지만, b에서 트리로 인식하고, a에서 find를
                //하면서 대표수 b를 출력하여 이미 이 트리는 체크했다고 판정한다.(실제론 없음
                if(fa==fb || (multy[fa] || multy[fb])){
                    multy[fa]=true;
                    multy[fb]=true;
                }
                else{
                    Union(a,b);
                }
            }

            int answer=0;
            for(int i=1; i<=n; i++){
                int temp=Find(i);
                if(!multy[temp]){
                    multy[temp]=true;
                    answer++;
                }
            }

            if(answer>1){
                bw.write("Case "+t+": A forest of "+answer+" trees.\n");
            }
            else if(answer==1){
                bw.write("Case "+t+": There is one tree.\n");
            }
            else{
                bw.write("Case "+t+": No trees.\n");
            }
        }
        bw.flush();
    }

    public static int Find(int v){
        if(num[v]==v){
            return v;
        }
        else{
            return num[v]=Find(num[v]);
        }
    }
    public static void Union(int a, int b){
        int fa=Find(a);
        int fb=Find(b);
        if(fa!=fb){
            num[fa]=fb;
        }
    }
}