각 테스트 케이스마다 트리의 갯수를 세서 형식에 맞게 출력하는 문제이다.
문제를 처음 접했을 때, 트리가 여러 개인 경우 "A forest of T trees."로 출력하라길래, '포레스트는 루트를 제거했을 때 서브트리들의 모임 아닌가?'라는 생각이 들었다.
하지만, 연결되지 않은 서로 독립된 트리들의 집합이었다는 것을 이 문제를 풀면서 알게 되었다.
아무튼 문제에서 요구한대로 테스트케이스마다 트리의 개수를 세야한다.
입력으로는 정점들의 연결 관계들이 주어지므로 그래프처럼 인접 행렬이나 인접 리스트로 표현해야 한다.
이렇게 표현해도 되는 이유는, 트리 자체가 방향이 없는 비순환 연결그래프이기 때문이다. 즉, 트리도 그래프의 일종이기 때문에 인접 행렬이나 인접 리스트로 표현이 가능하다는 것이다.
하지만, 어떤 정점들이 인접하는지 보다는 그래프를 탐색하면서 인접 정점으로 이동해야 하므로 인접 리스트로 표현하는 것이 효율적이다.
이렇게 트리를 표현할 방법을 결정했으니, 트리인지 판단하고 갯수를 세는 방법을 고민해보자.
앞서 언급했듯, 트리의 정의는 방향이 없는 비순환 연결그래프이다. 연결관계는 인접 리스트를 토대로 탐색할 때 방문한 정점들은 연결되어 있다고 볼 수 있으니 크게 신경쓰지 않아도 된다.
분리된 트리의 갯수를 세는 것이 우리의 목표이기 때문에, 연결되어 있지 않아 방문하지 않았다면 해당 집합은 독립적인 연결 그래프들의 집합이므로 해당 그래프들이 트리인지 판별하면 되기 때문이다.
다시 연결 그래프가 주어졌을 때, 트리를 판별하는 방법은 그래프를 탐색할 때, cycle이 존재하지 않으면 트리이고 그렇지 않으면 트리가 아니다.
즉, 트리는 부모가 아닌 정점을 재방문해서는 안된다는 의미이다.
따라서, 연결 그래프를 탐색하면서 부모와 방문 여부를 체크하고 부모가 아닌 인접 정점들에 대해, 재방문이 일어난 경우는 트리가 아니므로 BFS결과는 0이 되어야 한다.
하지만, 해당 그래프에 속한 모든 정점들은 트리가 될 수 없는 정점이므로 이를 모두 표시해 두어야 한다. 따라서, 중간에 return하지 않고 리턴 값만 으로 설정한 뒤, continue를 통해 해당 그래프에 속한 모든 정점을 방문했다고 표시해 놓자.
그렇게 해야, 탐색했던 그래프가 트리였든지 아니든지 상관 없이 다른 분리 집합의 정점을 시작점으로 설정하기 용이하기 때문이다.
이를 코드로 구현하면 다음과 같다.
#include <bits/stdc++.h>
using namespace std;
int n, m;
bool bfs(int st, vector<int> (&adj)[501], int p[], bool vis[]) {
bool ret = 1;
queue<int> q;
q.push(st);
vis[st] = 1;
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int nxt : adj[cur]) {
if (p[cur] == nxt) continue;
if (vis[nxt]) {
ret = 0;
continue;
}
q.push(nxt);
p[nxt] = cur;
vis[nxt] = 1;
}
}
return ret;
}
int solve(vector<int> (&adj)[501]) {
int cnt = 0, p[501];
bool vis[501] = {};
for (int i = 1; i <= n; i++) {
if (vis[i]) continue;
if (bfs(i, adj, p, vis)) cnt++;
}
return cnt;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
for (int tc = 1;; tc++) {
cin >> n >> m;
if (n == 0 && m == 0) break;
vector<int> adj[501];
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int cnt = solve(adj);
cout << "Case " << tc << ": ";
switch (cnt) {
case 0: cout << "No trees.";
break;
case 1: cout << "There is one tree.";
break;
default: cout << "A forest of " << cnt << " trees.";
}
cout << "\n";
}
}