[C/C++] 백준 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<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int n, m, u, v;
int ans, cnt;
bool visit[501];
vector<int> graph[501];

bool DFS(int x, int post_x)
{
	visit[x] = true;

	for (int i = 0; i < graph[x].size(); i++)
	{
		if (graph[x][i] == post_x) continue;

		if (visit[graph[x][i]]) return false;

		if (DFS(graph[x][i], x) == false) return false;
	}
	return true;
}

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

	while (true)
	{
		cin >> n >> m;
		if (n == 0 && m == 0) break;

		cnt++;
		ans = 0;
		for (int i = 1; i <= 500; i++)
		{
			graph[i].clear();
			visit[i] = false;
		}

		for (int i = 0; i < m; i++)
		{
			cin >> u >> v;
			graph[u].push_back(v);
			graph[v].push_back(u);
		}

		for (int i = 1; i <= n; i++)
		{
			if (!visit[i])
				if (DFS(i, 0)) ans++;
		}

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

 

 

 

www.acmicpc.net/problem/4803

4803번: 트리