문제
풀이
트리인지 확인하는 문제이다. 즉, 싸이클이 없는지 있는지를 체크하는 문제가 되겠다. 기존의 dfs를 이용하여 탐색하되, 돌아가는 경로가 있는지를 확인하기 위해서 그 전 node를 포함한채로 재귀를 진행했다. 만약 다음에 갈 곳과 그 전에 간 곳이 일치한다면 다시 역방향으로 가는 케이스이므로 무시해준다. 또 만약, 방문한 곳이 이미 방문한 곳이라면 이는 싸이클임이 확실하므로 false를 return 해준다. 그리하여 재귀적으로 call된 dfs중 false가 있다면 계속 false를 return하여 결국 최종적으로 선택한 처음 노드로 시작되는 경로가 tree가 아님을 출력한다. 이를 iteration방식으로 모든 노드에서 진행해준다. +) 추가로, 정점의 개수 - 1 = 간선의 갯수 인점을 이용한 코드도 Reference로 달아놓는다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <vector>
using namespace std;
vector<int> map[501];
int visited[501];
bool dfs(int curr, int before){
visited[curr] = true;
for(int i = 0; i<map[curr].size(); i++){
int next = map[curr][i];
if(next == before){
continue;
}
if(visited[next]){
return false;
}
if(dfs(next, curr) == false){
return false;
}
}
return true;
}
int main(){
int cnt = 1;
while(true){
int a, b;
scanf("%d %d", &a, &b);
if(a == 0 && b == 0){
return 0;
}
for(int i = 0; i<b; i++){
int from, to;
scanf("%d %d", &from, &to);
map[from].push_back(to);
map[to].push_back(from);
}
int T = 0;
for(int i = 1; i<=a; i++){
if(!visited[i]){
if(dfs(i, 0)) T++;
}
}
if(T>1){
printf("Case %d: A forest of %d trees.\n", cnt, T);
}
else if(T==1){
printf("Case %d: There is one tree.\n", cnt);
}
else{
printf("Case %d: No trees.\n", cnt);
}
cnt++;
for(int i = 1; i<=a; i++){
map[i].clear();
visited[i] = false;
}
}
}
