[C++] 백준 4803번: 트리

https://www.acmicpc.net/problem/4803

4803번: 트리

 

 > 풀이

트리를 체크하는 DFS 함수(setIsTree)를 짬으로써 해결할 수 있다.

방문한 적이 있는 노드에 방문한다는 것은 트리가 아니라는 것을 말해준다. 해당 조건을 만나더라도 DFS 함수를 끝까지 진행시켜서 isVisited가 올바른 정보를 담도록 해야한다. 이를 고려하여 global variable인 isTree의 값을 정해주는 식으로 설계하였다.

 

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

int n, m;
vector<int> graph[501];
bool isVisited[501];
bool isTree;

void setIsTree(int node, int prev) {
	if (isVisited[node]) {
		isTree = false;
		return;
	}

	isVisited[node] = true;

	int i;
	for (i = 0; i < graph[node].size(); i++) {
		int next = graph[node].at(i);
		if (next != prev) setIsTree(next, node);
	}
}

int getTreeCount() {
	int i, res = 0;

	for (i = 1; i < n + 1; i++) {
		if (!isVisited[i]) {
			isTree = true;
			setIsTree(i, 0);
			if (isTree) res += 1;
		}
	}

	return res;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int caseCount = 1;
	while (1) {
		int i;

		cin >> n >> m;
		if (n == 0 && m == 0) break;

		// 초기화
		for (i = 1; i < n + 1; i++) {
			graph[i].clear();
			isVisited[i] = false;
		}

		// 입력
		for (i = 0; i < m; i++) {
			int a, b;
			cin >> a >> b;
			graph[a].push_back(b);
			graph[b].push_back(a);
		}

		// Solution
		cout << "Case " << caseCount << ": ";

		int treeCount = getTreeCount();
		if (treeCount == 0) cout << "No trees.\n";
		else if (treeCount == 1) cout << "There is one tree.\n";
		else cout << "A forest of " << treeCount << " trees.\n";

		caseCount++;
	}

	return 0;
}