개요

백준 4803번: 트리

• 입력
  입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 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."를 테스트 케이스 번호와 함께 출력한다.

접근 방식

1. DFS나 BFS로 컴퍼넌트를 체크해서 노드갯수를 셀수는 있지만,
   간선갯수 체크를 어떻게 해야할지 몰랐다.
   트리도 노드갯수-간선갯수=1인 그래프면 트리가 성립된다는 성질을 모르고
   각 컴퍼넌트마다 싸이클을 이루는지 안 이루는지 체크해야 하는건가 하다가
   결국 검색했다.

2. 일단 상기한대로 그래프의 노드갯수-간선갯수가 1이 되면 싸이클이 발생하지 않는 트리가 된다.
   또한 간선갯수는 dfs에서 각 노드의 연결된 점을 for-each문으로 불러올때마다 edgeCnt변수를 증가시켜주면 총 간선갯수*2 값이 나온다.
   2배값이 나오는 이유는 양방향그래프로 인접노드를 서로 연결해주었으므로
   각 간선마다 중복해서 갯수가 증가하기 때문이다.
   따라서 마지막에 총 노드- 간선갯수/2를 한 값이 1이면 트리가 되는 것이다.
   다음은 DFS부분 함수이다.

   //각 컴퍼넌트의 노드 갯수 반환
   int DFS(int Node) {
   	//노드 갯수
   	int Sum = 1;
   	//해당 노드 방문했다면 0을 return해서 0 더해줌
   	if (visited[Node]) return 0;
   	//방문안했다면 방문 처리
   	visited[Node] = true;
   	for (int elem : adj[Node]) {
   		//각 연결된 점마다 edgeCnt++해줌 
   		//양방향그래프로 설정해놔서 간선갯수 2배니까 마지막에 /2해줘야함
   		edgeCnt++;
   		//node갯수 더해줌
   		Sum+=DFS(elem);
   	}
   	//Sum 리턴해줌
   	return Sum;
   	
   }

   다음은 모든 노드에서 DFS를 실행하는 Solution함수이다.

   void Solution(int testCases) {
   	//testCases번호의 테케에서 트리 갯수
   	int trees = 0;
   	//노드 갯수만큼 dfs로 컴퍼넌트 체크 
   	for (int i = 1; i <= N; i++) {
   		//i 노드 방문했다면 continue
   		if (visited[i]) continue;
   		//노드갯수 0으로 설정
   		int Nodes = 0;
   		//간선 갯수인 cnt0으로 초기화
   		edgeCnt = 0;
   		//노드갯수 재귀통해 구함
   		Nodes+=DFS(i);
   		//그래프를 양방향그래프로 선언해서 간선이 두개씩 체크되서 cnt가 두배가 되므로 2로 나눠줘야함.
   		//노드갯수-간선갯수가 1이여야 트리가 성립함
   		if (Nodes - edgeCnt / 2 == 1 ) trees++;
   	}
   	if (trees == 0) cout << "Case " << testCases << ": No trees."<<'\n';
   	else if (trees == 1) cout << "Case " << testCases << ": There is one tree."<<'\n';
   	else cout << "Case " << testCases << ": A forest of " << trees << " trees."<<'\n';
   }

전체코드

#include<iostream>
#include<vector>

using namespace std;

vector<vector<int>> adj;
bool visited[501];
int N=0, M = 0,tmpNode1=0,tmpNode2=0,edgeCnt=0;

void Solution(int testCases);

void Input() {
	//테스트케이스 번호 출력용
	int testCases = 1;
	while (1) {
		//각 반복마다 clear초기화
		adj.clear();
		//visited배열 초기화
		fill(visited, visited + 501, false);

		//N,M 입력받음
		cin >> N >> M;

		if (N == 0 && M == 0)
			return;
		else {
			//adj 크기 할당해줌
			adj.resize(N + 1);
			//M만큼 반복
			for (int i = 0; i < M; i++) {
				cin >> tmpNode1 >> tmpNode2;
				//node1에 node2연결
				adj[tmpNode1].push_back(tmpNode2);
				//node2에 node1연결
				adj[tmpNode2].push_back(tmpNode1);
			}
		}

		Solution(testCases++);
	}
}
//각 컴퍼넌트의 노드 갯수 반환
int DFS(int Node) {
	//노드 갯수
	int Sum = 1;
	//해당 노드 방문했다면 0을 return해서 0 더해줌
	if (visited[Node]) return 0;
	//방문안했다면 방문 처리
	visited[Node] = true;
	for (int elem : adj[Node]) {
		//각 연결된 점마다 edgeCnt++해줌 
		//양방향그래프로 설정해놔서 간선갯수 2배니까 마지막에 /2해줘야함
		edgeCnt++;
		//node갯수 더해줌
		Sum+=DFS(elem);
	}
	//Sum 리턴해줌
	return Sum;
	
}

void Solution(int testCases) {
	//testCases번호의 테케에서 트리 갯수
	int trees = 0;
	//노드 갯수만큼 dfs로 컴퍼넌트 체크 
	for (int i = 1; i <= N; i++) {
		//i 노드 방문했다면 continue
		if (visited[i]) continue;
		//노드갯수 0으로 설정
		int Nodes = 0;
		//간선 갯수인 cnt0으로 초기화
		edgeCnt = 0;
		//노드갯수 재귀통해 구함
		Nodes+=DFS(i);
		//그래프를 양방향그래프로 선언해서 간선이 두개씩 체크되서 cnt가 두배가 되므로 2로 나눠줘야함.
		//노드갯수-간선갯수가 1이여야 트리가 성립함
		if (Nodes - edgeCnt / 2 == 1 ) trees++;
	}
	if (trees == 0) cout << "Case " << testCases << ": No trees."<<'\n';
	else if (trees == 1) cout << "Case " << testCases << ": There is one tree."<<'\n';
	else cout << "Case " << testCases << ": A forest of " << trees << " trees."<<'\n';
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();
}

문풀후생

그래프에서 트리를 구별하는 법과 간선, 노드를 구하는 방법을 알게된 문제였다.
다른 방법을 찾아보니 BFS방식으로 탐색하며,
만약 다음 노드가 이미 방문을 한 상태면서,
이전 노드와 다르면 싸이클이 생긴 것을 알수 있게 구현한 방식도 있었다.
바로 트리인지 판별하여 답을 출력하는 방식이라 해당 방식도 좋아보였다.