문제 이해

그래프가 주어졌을 때, 트리의 개수를 세는 문제이다.

---

문제 풀이

트리의 성질 중 "트리의 Node 개수 = 트리의 Edge 개수 + 1"라는 것이 있다.
이 성질을 통해 문제를 해결했다.

먼저 visit하지 않은 점 하나를 Select한다.

이후 이 점을 시작으로 DFS나 BFS를 시작한다. 이 과정에서 Node의 개수와 Edge의 개수를 구한다.

마지막으로 트리의 Node 개수와 트리의 Edge개수를 비교하여, 만약 트리의 성질을 만족한다면 트리의 개수를 하나 추가해주면 될 것이다.

---

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N,M;
	static ArrayList<Integer>[] nodes;
	static boolean[] visit;
	static int node, edge;

	static void dfs(int start){
		// dfs 과정
		if(visit[start]) return;
		
		visit[start] = true;
		edge+=nodes[start].size();
        // 그래프의 Edge 개수 추가
        // 여기서, nodes[start]에는 자식 Node뿐만이 아닌 부모 Node의 값까지 
        // 포함되어 있다.
        // 이 "부모 Node 개수"까지 Edge 개수에 더해진다는 점을 유의하자
		node++;
        // 그래프의 노드 개수 추가
		
		for(int s:nodes[start]) {
			dfs(s);
		}
	}
	
	
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		
		int situ = 0;
		while(true) {
			situ++;
			N = sc.nextInt();
			M = sc.nextInt();
			
			if(N==0 && M==0) break;
			
			nodes = new ArrayList[N+1];
			visit = new boolean[N+1];
			
			for(int i =1;i<N+1;i++) {
				nodes[i] = new ArrayList<>();
			}
			
			for(int i =0;i<M;i++) {
				int tmp1 = sc.nextInt();
				int tmp2 = sc.nextInt();
				
				nodes[tmp1].add(tmp2);
				nodes[tmp2].add(tmp1);
			}
			int T  =0;
			for(int i =1;i<N+1;i++) {
				if(visit[i]) continue;
				edge = 0;
				node = 0;
				dfs(i);
				if(edge==(node-1)*2) T++;
                /*
                edge에는 자식 노드의 수도 저장되어 있지만, 
                부모 노드의 수도 같이 저장되어 있다.
                
                트리의 경우, 자식 A ~ 부모 Edge가 1개 존재한다면 
                부모 ~ 자식 A Edge도 1개만 존재한다.
                
                즉, 원래라면 Tree는 edge = (node-1)이 성립해야 하지만, 
                edge는 중복하여 2번씩 더해졌으므로 edge = (node-1) * 2일 때 
                Tree의 성질을 만족하는 것이다.
                */
			}

			sb.append("Case "+situ+": ");
			
			switch(T) {
			case 0:
				sb.append("No trees.").append("\n");
				break;
			case 1:
				sb.append("There is one tree.").append("\n");
				break;
			default:
				sb.append("A forest of ").append(T).append(" trees.")
                                                   .append("\n");
				break;
			}
		}
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 3번째 줄 틀렸습니다 : Tree의 특성 중 A ⇒ B로 가는 Path는 무조건 하나만 존재한다 라는 특성을 이용하려 했으나 알고리즘을 잘못 짜 틀렸다.

• 2번째 줄 틀렸습니다 : edge = (node-1) * 2가 아닌 edge = (node-1)로 맞춰보고 싶어 도전해봤지만, 알고리즘이 복잡해져 틀렸다.