[4803번] 트리

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 트리 정의

2. BFS

이 문제에 녹아있는 내용은 다음과 같다.

1. 무방향 그래프가 주어졌을 때 트리가 존재하는가?

2. 트리가 존재한다면 트리는 몇개인가?

3. 트리가 존재한다면 각 트리마다의 정점과 간선의 개수는 몇개인가?

나름 트리 문제중 좋은 문제라 생각이 든다.

우선 vector를 통해 정점과 간선의 정보를 받아내고

BFS를 통해 정점에서 다른 정점으로의 탐색을 통해 트리를 파악한다.

                // 트리이기 위해서는 '간선 / 2 == 정점 - 1' 이어야 한다.

                if (edge / 2 != vertex - 1)

                    cnt--  ; 

가장 중요한 내용은 이 코드이다.

트리의 가장 기본적인 정의인데, 트리이기 위해서는

방향이 있는 트리일 경우 :: 간선 == 정점 - 1

방향이 없는 트리일 경우 :: 간선/2 == 정점 - 1이라는 것이다.

이 문제는 트리에 대한 정의부터 다시 돌아볼 수 있는 기회를 주는 문제인 것 같다.

다른 내용은 소스 코드 주석으로 달아두었다.

소스 코드 : 

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 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93

#include <iostream> #include <cstdio> #include <vector> #include <queue>   using namespace std;   int main() {     int n, m;     int from, to, val;     int tcase = 0;     while (1)     {         scanf("%d %d", &n, &m);           if (n == 0 && m == 0)             return 0;           vector<int> vc[1002];         queue<int> q;         bool visited[1002];           fill(visited, visited + 1002, false);           int cnt = 0;           while (m--)         {             scanf("%d %d", &from, &to);                          vc[from].push_back(to);             vc[to].push_back(from);         }           // 하나의 노드 혹은 사이클에 대해 V, E를 알 수 있게 된다.         for (int i = 1; i <= n; i++)         {             // 방문한 적 없는 노드는 방문             // (cnt에 의해 연결 요소의 개수가 정해진다.)             // (연결 요소의 개수 :: 트리 + 사이클)             int edge = 0;             int vertex = 0;             if (visited[i] == false)             {                 cnt++;                   q.push(i);                   while (!q.empty())                 {                     int here = q.front();                     q.pop();                       // 이 조건문을 통해 정점의 개수를 알 수 있다.                     // 방문한 적이있는 정점이면 정점에 추가 해주지 않는다는 것                     if (visited[here])                         continue;                       vertex++;                     visited[here] = true;                       // 양방향 그래프의 간선이 추가된다.                     for (int j = 0; j < vc[here].size(); j++)                     {                         edge++;                         q.push(vc[here][j]);                     }                 }                                  // 트리이기 위해서는 '간선 / 2 == 정점 - 1' 이어야 한다.                 if (edge / 2 != vertex - 1)                     cnt--;                   edge = 0;                 vertex = 0;             }         }             if (cnt >= 2)             printf("Case %d: A forest of %d trees.\n", ++tcase, cnt);         else if (cnt == 1)             printf("Case %d: There is one tree.\n", ++tcase);         else             printf("Case %d: No trees.\n", ++tcase);     }       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus