백준 4803번 트리

문제

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

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

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

사용한 알고리즘 : DFS

DFS 탐색을 통해 Tree 인지 판별하는 함수를 하나 만들어 줍니다.

아직 탐색되지 않은 노드가 있는 경우, 해당 노드를 root로 하는 tree를 과정(1) 에서 만든 함수로 만들어 주고, tree가 만들어 졌다면, 정답+1 해줍니다.

	#include <bits/stdc++.h>
	using namespace std;

	int N, M, cnt;
	bool visited[555];
	vector<int> adj[555];

	bool DFS(int curr, int justbefore) {
	visited[curr] = true;

	for (auto child : adj[curr]) {
	if (child == justbefore) continue;
	// cycle 이 생기면
	if (visited[child]) return false;
	if (DFS(child, curr) == false) return false;
	}
	return true;
	}
	int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	while (1) {
	cin >> N >> M;
	if (N == 0 && M == 0) break;

	// 초기화
	int ans = 0; // 트리 개수
	memset(visited, false, sizeof(visited));
	for (int i = 1; i <= N; ++i) adj[i].clear();

	for (int i = 0; i < M; ++i) {
	int a, b;
	cin >> a >> b;
	adj[a].push_back(b);
	adj[b].push_back(a);
	}
	for (int i = 1; i <= N; ++i)
	if (!visited[i])
	if (DFS(i, 0)) ans++;

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

view raw BOJ 4803.cpp hosted with ❤ by GitHub