BOJ 4803: 트리

#BOJ 4803: 트리

4803번: 트리

#풀이

간선들을 입력받아 트리가 몇개 있는지 확인하는 문제이다. 

 

트리는 사이클을 있는지 확인하면 된다.

 

사이클을 확인하는 방법은 DFS나 BFS로 정점들을 탐색해가며 방문한 정점을 방문하면 사이클을 한다는 것을 판단할 수 있다.

 

트리이므로 부모의 정점을 확인 후 부모가 아닌 정점을 찾아야 한다.

 

나는 맨 처음에 부모 배열을 안만들고 계속 부모 정점을 바꾸고 하여 계속 틀렸다고 나와 멘붕이 왔다. ㅋㅋㅋㅋ

그래도 차근 차근 읽어보니까 어디가 문제였는지 찾을 수 있었다.

 

#코드

#include<iostream>
#include<vector>
#include<string>
#include<queue>
using namespace std;
int n , m;
vector<int>adj[501];
int vis[501]; // 방문
int prt[501]; // 부모
int bfs(int i) {
	if (vis[i] != 0)
		return 0;
	int ans = 0;
	queue<int> q;
	q.push(i);
	vis[i] = 1;
	prt[i] = 0;
	while (!q.empty()) {
		int prv = q.front(); q.pop();
		for (auto nxt : adj[prv])
		{
			if (nxt == prt[prv]) // prv의 부모인지 확인
				continue;
			if (vis[nxt] != 0) // 사이클을 찾은 것이므로 트리가 아님
				return 0;

			prt[nxt] = prv;
			vis[nxt] = 1;
			q.push(nxt);
		}
	}
	return 1;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int case_num = 1;
	while (1)
	{
		string str = "";
		cin >> n >> m;
		if (n == 0 && m == 0)
			break;
		for (int i = 0; i < m; i++) {
			int num1, num2;
			cin >> num1 >> num2;
			adj[num1].push_back(num2);
			adj[num2].push_back(num1);
		}
		int tree_num = 0;
		for(int i = 1; i <=n; i++)
			tree_num += bfs(i);

		if (tree_num == 1)
			str = "There is one tree.";
		else if (tree_num == 0)
			str = "No trees.";
		else {
			str = "A forest of " + to_string(tree_num) + " trees.";
		}

		cout << "Case " << case_num << ": " << str << '\n';
		case_num++;

		fill(vis + 1, vis + n + 1, 0);
		for (int i = 1; i <= n; i++) {
			adj[i].clear();
		}
	}

	return 0;
}