트리
문제
그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.
트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다.
그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오.
풀이
- dfs로 탐색을 하면서 싸이클이 인식이 안되면 tree로 인식한다.
- 탐색되지 않은노드가 없을때 까지 반복한다.
고민했던 점
루트가 고정되어있지 않은 부분이 신경쓰였다. 만약 
이렇게 생긴 트리에서 "5" 부터 탐색을 시작한다면 5 1 6을 탐색하고, 10을 기준으로 탐색할때
이미 탐색했던 노드가 있으니 싸이클로 인식해 오답이 될거같았다.
하지만 여기서 입력되는 간선은 양방향이므로, 5 1 6에서 끝나지않고 10까지, 그뒤 이어서 17 14 21까지 탐색을 완료하게 되므로 신경쓰지 않아도 된다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>
#include <string.h>
#include <queue>
using namespace std;
#define endl "\n"
#define MAX 500+1
vector<int> graph[MAX];
bool visited[MAX];
int ans, cnt;
int n, m, u, v;
bool dfs(int x,int postX) {
visited[x] = true;
for (int i = 0; i < graph[x].size(); i++)
{
int child = graph[x][i];
if (child==postX)
{
continue;
}
else if (visited[child])
{
return false;
}
else {
if (!dfs(child, x)) {
return false;
}
}
}
return true;// tree
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
//ifstream cin; cin.open("input.txt");
while (true)
{
cin >> n >> m;
if (n==0 && m==0)
{
break;
}
cnt++;
for (int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
for (int i = 1; i <= n; i++)
{
if (!visited[i])
{
if (dfs(i,0))
{
ans++;
}
}
}
cout << "Case " << cnt << ": ";
if (ans==0)
{
cout << "No trees." << endl;
}
else if (ans==1)
{
cout << "There is one tree." << endl;
}
else {
cout << "A forest of " << ans << " trees." << endl;
}
ans = 0;
memset(graph, 0, sizeof(graph));
memset(visited, false, sizeof(visited));
}
}