[백준] 4803. 트리

문제

그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다.

그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n ≤ 500과 m ≤ n(n-1)/2을 만족하는 정점의 개수 n과 간선의 개수 m이 주어진다. 다음 m개의 줄에는 간선을 나타내는 두 개의 정수가 주어진다. 같은 간선은 여러 번 주어지지 않는다. 정점은 1번부터 n번까지 번호가 매겨져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다.

출력

입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다.

 

 

#include<bits/stdc++.h>
using namespace std;
int N, M, cnt, tc = 1;
vector<int>adj[501];
int v[501];

bool dfs(int k,int ret) { //ret은 바로 이전 노드입니다. 바로이전 노드로 돌아가는경우를 막습니다
	if (v[k])return false;
	v[k] = 1;
	for (auto r : adj[k]) {
		if (r == ret)continue;
		if (!dfs(r,k))return false;
	}
	return true;
}
int main() {
	while (cin >> N >> M) {
		if (N == 0 && M == 0)break;
		for (int i = 0; i <= 500; i++)adj[i].clear();
		memset(v, 0, sizeof(v));
		cnt = 0;
		int a, b;
		while (M--) {
			cin >> a >> b;
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		for (int i = 1; i <= N; i++) {
			if (!v[i])
				if (dfs(i,0))cnt++;
		}
		cout << "Case " << tc << ": ";
		if (cnt == 1)cout << "There is one tree.\n";
		else if (cnt == 0)cout << "No trees.\n";
		else cout << "A forest of " << cnt << " trees.\n";
		tc++;
	}
}

트리란 사이클이 없는 연결요소입니다.

따라서 한 노드에대해서 DFS를 수행하고, 만약 사이클 즉 이미 방문한 요소를 다시 방문한 경우 사이클이 발생한것이므로

false를 반환하면 됩니다.