[백준] 4803번 - 트리 (C++) 문제 및 풀이

문제) 백준 - DFS - 트리

https://www.acmicpc.net/problem/4803

4803번: 트리

 

1번 노드부터 탐색하면서 트리의 개수를 계산합니다. 그래프에서 노드의 개수와 간선의 개수를 계산하여 cntEdge(i) / 2 == cntNode(i) - 1을 통해 트리 여부를 판별합니다.

 

 

C++ 소스코드)

	// Node
	int cntNode(int now){
	int cnt = 1;
	visited[now] = true;
	for(int next: graph[now])
	if(!visited[next])
	cnt += cntNode(next);
	return cnt;
	}
	// Edge
	int cntEdge(int now){
	int cnt = graph[now].size();
	finished[now] = true;
	for(int next: graph[now])
	if(!finished[next])
	cnt += cntEdge(next);
	return cnt;
	}

view raw 4803.cpp hosted with ❤ by GitHub

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/4803_%ED%8A%B8%EB%A6%AC.cpp

GitHub - Chocochip101/BOJ_Solution: BOJ Solutions