C++ 백준 4803 트리

백준 4803

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

4803번: 트리

풀이 전 나의 생각

그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성해야 한다.

 

조건

- n ≤ 500

- m ≤ n(n-1)/2

 

과정

주어진 조건들은 입출력의 값에 관한 것들이기 때문에 크게 신경쓰지 않아도 된다.

 

이 문제에서 신경써야할 것은 트리는 사이클이 없는 연결 요소라는 것이다.

 

그럼 이 문제에서 신경써야 할 부분은 트리의 사이클이 존재하는 부분을

찾아내어 트리의 조건을 만족하지 못한다는 것을 알려줘야 한다.

 

이를 BFS를 이용하여 인접한 정점을 방문하며 조건에 따라

트리가 될 수 있는 여부를 반환해줄 것이다.

 

1. 인접한 정점들을 탐색하기 위해 간선의 정보를 저장해준다.

vector<vector<int>> linkvec(n + 1);

		for (int i = 0; i < m; i++)
		{
			int f, s;
			cin >> f >> s;

			linkvec[f].push_back(s);
			linkvec[s].push_back(f);
		}

(1, 2) 와 (2, 3) 이 저장됐을 때 [1] = 2, [2] = 1, 3이 저장된다.

 

2. 첫 정점 부터 탐색을 진행하며 트리의 여부를 확인한다.

for (int start = 1; start <= n; start++)
		{
			if (visted[start] == 0)
			{
				if (bfs(linkvec, start)) ans++;
			}
		}

 

3. 트리의 사이클을 확인하며 트리의 조건을 만족하는지 확인한다.

for (auto next : linkvec[cur])
		{
			if (visted[next] != 0 && visted[next] != visted[cur] - 1)
			{
				tree = false;
			}

			if (visted[next] != 0) continue;
				visted[next] = visted[cur] + 1;
				q.push(next);
		}

인접한 노드가 이미 방문을 했고, 부모 노드가 아니라면 사이클이 존재한다는 것을 의미한다.

하지만 인접한 노드가 이미 방문을 했고, 부모 노드라면 그냥 패스해준다.

 

예를 들어 (1, 2) 가 들어 왔을 때 visted[1] = 1, visited[2] = 2가 될 것이다.

다음으로  (2, 3) 이 들어와서 2의 인접 정점인 1, 3 중 1을 탐색할 때 visited[1] == visited[2] - 1
즉, 1 == 2 - 1 이기 때문에 자신의 부모 노드임을 확인할 수 있다. (인접한 정점 방문)

따라서 트리의 사이클이 존재하는 것이 아니기 때문에 따로 표시를 해주지 않고 넘어간다.

 

만약 다음으로 (1, 3)의 값이 들어온다면 visited[3] == visited[1] - 1 , 3  != 1 - 1 이기 때문에 
1, 2, 3이 서로 사이클을 이뤄 버린다는 것을 의미한다. (인접하지 않은 정점 방문)

 

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

int visted[501];

bool bfs(vector<vector<int>> linkvec, int start)
{
	queue<int> q;
	q.push(start);
	visted[start] = 1;

	bool tree = true;

	while (!q.empty())
	{
		int cur = q.front();
		q.pop();

		for (auto next : linkvec[cur])
		{
			if (visted[next] != 0 && visted[next] != visted[cur] - 1)
			{
				tree = false;
			}

			if (visted[next] != 0) continue;
				visted[next] = visted[cur] + 1;
				q.push(next);
		}
	}
	return tree;
}

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

	int c = 1;

	while (true)
	{
		int n, m; 
		cin >> n >> m;

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

		vector<vector<int>> linkvec(n + 1);

		for (int i = 0; i < m; i++)
		{
			int f, s;
			cin >> f >> s;

			linkvec[f].push_back(s);
			linkvec[s].push_back(f);
		}

		fill(visted, visted + 501, 0);

		int ans = 0;

		for (int start = 1; start <= n; start++)
		{
			if (visted[start] == 0)
			{
				if (bfs(linkvec, start)) ans++;
			}
		}

		cout << "Case " << c++ << ": ";
		if (ans > 1) cout << "A forest of " << ans << " trees.";
		else if (ans == 1) cout << "There is one tree.";
		else cout << "No trees.";
		cout << '\n';
	}
}