[boj : 4803] 트리

www.acmicpc.net/problem/4803

4803번: 트리

문제 : 트리의 개수를 구해라. (이때, x==y 인 조건은 배제해도 된다. 적어도 이 문제에는 x==y인 데이터는 존재하지 않음)

 

해설 : 뭐 각자 선호하는 방식으로 풀면 된다. disjoint-set 개념을 이용해도 되고 dfs를 이용해서 구해도 되고.

저는 dfs로 구했습니다. 이때 트리라는 것을 체크하는 방법이 여러가지 존재한다고 하네요. 

전 끝까지 갔을때 싸이클이 존재하면 false를 존재하지 않는다면 true를 return 시켜 & 연산으로 판별해주었습니다.

 

다른 방법은 트리는 n개의 정점이 주어지고 항상 간선의 개수는 n-1개라는 것 입니다.

그럼 어느 정점으로 들어가게 되고 그 정점에 붙어있는 간선의 개수를 더해줍니다. 그리고 (정점의 개수)*2 = (간선의 개수) 라면 트리, 아니면 트리가 아니다라고 판별해주면 됩니다.

 

#include<bits/stdc++.h>

using namespace std;

int n, m;
int memo[510];
vector<int> v[510];

bool dfs(int x,int prev);

int main()
{
	int cnt, t = 1;
	while (true) {
		cnt = 0;
		int x, y;
		cin >> n >> m;
		if (n == 0 && m == 0)break;
		for (int i = 0; i < m; i++) {
			cin >> x >> y;
			v[x].push_back(y);
			v[y].push_back(x);
		}
		for (int i = 1; i <= n; i++)
			if (!memo[i]) {
				if (dfs(i, -1)) cnt++;
			}
		if (cnt == 1)
			printf("Case %d: There is one tree.", t);
		else if(cnt>1)
			printf("Case %d: A forest of %d trees.", t,cnt);
		else
			printf("Case %d: No trees.", t);
		cout << "\n";
		memset(memo, 0, sizeof(memo));
		for (int i = 1; i <= n; i++)
			v[i].clear();
		t++;
	}
	return 0;
}
bool dfs(int x,int prev)
{
	bool ret = true;
	if (memo[x] == 1) 
		return false; 	
	memo[x] = 1;
	for (int i = 0; i < v[x].size(); i++)
		if(prev!=v[x][i])
			ret &= dfs(v[x][i],x);
	return ret;
}