백준 / 4803 트리 C++

www.acmicpc.net/problem/4803

4803번: 트리

주어진 그래프에 트리가 몇 개 있는지 찾는 문제입니다. 처음에는 루트 노드마다 dfs를 이용하면서 사이클 유무를 판별하려 했으나 20% 가량 맞다가 메모리 초과가 나서 해결해보려 했지만 실패하였습니다.

 

그래서 트리의 특징인 정점 N개, 간선 N-1개를 이용하여 풀었습니다.

마찬가지로 dfs를 이용하여 정점의 개수와 간선의 개수를 체크하고, 각각 N, N-1개를 만족하면 됩니다. 

간선의 개수를 셀 때 간단히 생각하여 해당 노드와 연결된 모든 간선의 개수를 세도록 만들어 계산 결과는 실제 간선의 개수 X 2가 됩니다. (양방향 그래프처럼 생각)

 

코드는 다음과 같습니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>

using namespace std;

int n, m;
vector<int>tree[501];
bool Vcheck[501]; // vertex 체크
bool Echeck[501]; // edge 체크
int Vcnt; // 트리에 연결된 노드 개수
int Ecnt; // 트리에 연결된 간선 개수 X 2
int Tcnt; // 전체 트리 개수

void make_tree()
{
	cin >> n >> m;

	for (int i = 0; i < 501; i++)
	{
		tree[i].clear();
	}

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

	memset(Vcheck, false, sizeof(Vcheck));
	memset(Echeck, false, sizeof(Echeck));
	Vcnt = 0;
	Ecnt = 0;
	Tcnt = 0;
}

// 트리 조건 : vectex N개 => edge N-1개
// dfs로 root노드에서부터 연결된 노드 개수 체크 
void vertex_num(int node) 
{
	Vcheck[node] = true;
	Vcnt++;

	for (int i = 0; i < tree[node].size(); i++) {
		int next_node = tree[node][i];
		if (!Vcheck[next_node]) {
			vertex_num(next_node);
		}
	}
}

// dfs로 root노드에서부터 연결된 간선 개수 체크
// 단순히 노드별로 연결된 간선 개수 모두 계산하므로 Ecnt = 실제 간선 X 2
void edge_num(int node)
{
	Echeck[node] = true;
	Ecnt += tree[node].size();

	for (int i = 0; i < tree[node].size(); i++) {
		int next_node = tree[node][i];
		if (!Echeck[next_node]) {
			edge_num(next_node);
		}
	}
}

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

	int idx = 0;
	while (1)
	{
		make_tree();
		idx++;
		
		if (n == 0 && m == 0)
			break;

		for (int i = 1; i <= n; i++) {
			if (!Vcheck[i]) {

				Vcnt = 0;
				Ecnt = 0;

				vertex_num(i);
				edge_num(i);

				// 트리인지 확인
				if ((Vcnt - 1) == (Ecnt / 2)) {
					Tcnt++;
				}
			}
		}

		if (Tcnt == 0) {
			cout << "Case " << idx << ": No trees.\n";
		}
		else if (Tcnt == 1) {
			cout << "Case " << idx << ": There is one tree.\n";
		}
		else {
			cout << "Case " << idx << ": A forest of " << Tcnt << " trees.\n";
		}
	}
}