[백준] 4803번 : 트리

문제

 

 

접근 방식

그래프가 주어졌을 때 해당 그래프에 트리가 몇 개 존재하는지를 구하는 문제다.

 

즉, 하나의 정점에서 출발하여 갈 수 있는 모든 정점까지 갔을 때

사이클이 존재하지 않으면 하나의 트리라고 볼 수 있고

이렇게 탐색을 했을 때 방문한 정점이 n개, 간선이 n-1개라면

트리라는 것을 알 수 있다.

 

무방향 그래프에서 트리를 찾는 것이기 때문에 (n - 1) * 2개의 간선이

있는지 확인하여 맞다면 트리의 개수를 1씩 증가시켜주면 된다.

 

정점을 처음 방문할 때마다 정점의 개수를 카운팅 해주고

해당 정점에 있는 모든 간선을 확인할 때마다 간선의 개수를 카운팅 하고

아직 방문하지 않은 정점인 경우에만 방문해준다.

 

한 정점에서의 탐색이 모두 끝났다면

현재까지 기록된 정점과 간선의 개수가

트리의 기준에 만족하는지 확인해주면 된다.

 

풀이

public class Main {

	private static int cnt, node, edge;
	private static ArrayList<ArrayList<Integer>> near;
	private static boolean[] isVisited;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		int c = 1, n, m, x, y;

		while (true) {
			st = new StringTokenizer(br.readLine());

			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());

			if (n + m == 0) break;

			cnt = 0;
			near = new ArrayList<>();
			isVisited = new boolean[n + 1];

			for (int i = 0; i <= n; i++) {
				near.add(new ArrayList<>());
			}

			for (int i = 0; i < m; i++) {
				st = new StringTokenizer(br.readLine());

				x = Integer.parseInt(st.nextToken());
				y = Integer.parseInt(st.nextToken());

				near.get(x).add(y);
				near.get(y).add(x);
			}

			for (int i = 1; i <= n; i++) {
				if (isVisited[i]) continue;
				node = 0;
				edge = 0;
				dfs(i);
				if (edge == (node - 1) * 2) cnt++;
			}

			sb.append("Case ").append(c++).append(": ");

			if (cnt == 0) sb.append("No trees.");
			else if (cnt == 1) sb.append("There is one tree.");
			else sb.append("A forest of ").append(cnt).append(" trees.");

			sb.append("\n");
		}

		System.out.println(sb);
	}

	private static void dfs(int cur) {
		isVisited[cur] = true;
		node++;

		for (int next : near.get(cur)) {
			edge++;
			if (isVisited[next]) continue;
			dfs(next);
		}
	}
}