BOJ 4803 트리

1 개요

BOJ 4803 트리

• 백준 온라인 저지 4803번 문제
• BOJ 35단계

2 C++

#include <bits/stdc++.h>
using namespace std;

int N, M;
bool visited[503];
vector<int> A[503];

bool dfs(int index, int parentIndex) {
	visited[index] = true;
	for (auto& head: A[index]) {
		if (!visited[head]) {
			if (dfs(head, index)) return true;
		} else {
		    if (parentIndex != head) return true;
		}
	}
	return false;
}

void solve(int cas) {
	memset(visited, false, sizeof(visited));
	int answer = 0;
	for (int i = 1; i <= N; i++) {
		if (!visited[i]) {
			if (!dfs(i, -1)) answer++;
		}
	}
	cout << "Case " << cas << ": ";
	if (answer == 0) {
	    cout << "No trees.";
	} else if (answer == 1) {
	    cout << "There is one tree.";
    } else {
        cout << "A forest of " << answer << " trees.";
    }
    cout << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int cas = 1;
	while(true) {
		cin >> N >> M;
		if (N == 0 && M == 0) break;
		for (int i = 1; i <= 500; i++) {
		    A[i].clear();
		}
		int a, b;
		while (M--) {
			cin >> a >> b;
			A[a].push_back(b);
			A[b].push_back(a);
		}
		solve(cas);
		cas++;
	}
}