https://www.acmicpc.net/problem/4803
트리 순회 시 dfs를 이용하였다. 사이클을 형성하는지 확인하기에 bfs는 적절하지 않다. dfs는 직전에 탐색한 부모 노드를 기억해두고, 현재 탐색하는 노드가 1) 직전 노드가 아니며 2) 방문한 적 없는 노드인지 확인하여 사이클을 만드는지 아닌지 알 수 있다.
#include <iostream>
#include <vector>
using namespace std;
void printResult(int cnt, int t) {
cout << "Case " << t << ": ";
switch(cnt) {
case 0: cout << "No trees."; break;
case 1: cout << "There is one tree."; break;
default: cout << "A forest of " << cnt << " trees."; break;
}
cout << "\n";
return;
}
void dfs(bool& cycle, int cur, int prev, vector<vector<int>>& graph, vector<bool>& visited) {
if(visited[cur]) {
cycle = true;
return;
}
visited[cur] = true;
for(int next : graph[cur]) {
if(next == prev) continue;
dfs(cycle, next, cur, graph, visited);
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n, m, a, b, t=0;
while(++t) {
cin >> n >> m;
if(!n && !m) break;
vector<vector<int>> graph(n+1);
for(int i=0; i<m; i++) {
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
int cnt = 0;
vector<bool> visited(n+1, false);
for(int i=1; i<=n; i++) {
if(visited[i]) continue;
bool cycle = false;
dfs(cycle, i, 0, graph, visited);
if(!cycle) cnt++;
}
printResult(cnt, t);
}
return 0;
}