BOJ(백준) 4803 - 트리

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

---

자료구조(트리), 연결요소,

그래프의 정점과 간선이 주어지면, 포레스트(트리의 집합)속에서 트리의 갯수를 찾는 프로그램을 작성하라.

---

시간복잡도 : O(N)

N은 포레스트 내에 정점 개수. 연결요소 검사를 하고나서 다시 중복으로 확인하지 않는다.

---

점검해봐야 할 부분

-자료구조를 왜 깊게 공부해야 하는지 교훈을 주는 문제. (노드의 개수 = 간선의 개수 - 1)

+순수 자료구조의 속성에 대해 증명해보고 체화되어있지 않으면 문제를 너무 어렵게 풀게 된다.

- 트리는 방향성 없는 상태에서 사이클이 없는 연결요소라는 개념

- 그래프와 트리에서의 사이클 판단은 다르다.

- 사이클찾는 아이디어(visit, finish 자료구조)

? 총 연결요소 개수 - 사이클 개수 = 트리의 개수 성립하는지

---

https://github.com/jongwuner/Algorithm/blob/master/BOJ/4803.cpp

#include<iostream>
#include<vector>
#include<cstring>
#define MAX 550
using namespace std;
int N, M, T, pre[MAX], edgeCnt;
bool visit[MAX];
vector<int> adj[MAX];
int DFS(int idx) {
    int cnt = 0;
    visit[idx] = true;
    for (int i = 0; i < adj[idx].size(); i++) {
        int next = adj[idx][i];
        if (!visit[next]) {
            cnt += DFS(next);
        }
    }
    edgeCnt += adj[idx].size();
    return cnt + 1;
}
int main() {
    while (scanf("%d %d", &N, &M), (N || M)) {
        int cnt = 0;
 
        memset(visit, false, sizeof(visit));
        memset(pre, -1, sizeof(pre));
        for (int i = 0; i < MAX; i++) adj[i].clear();
 
        for (int i = 1, a, b; i <= M; i++) {
            scanf("%d %d", &a, &b);
            adj[a].push_back(b); adj[b].push_back(a);
        }
 
        for (int i = 1; i <= N; i++) {
            if (!visit[i]) {
                edgeCnt = 0;
                if (DFS(i) - 1 == edgeCnt / 2) {
                    cnt++;
                }
            }
        }
 
        T++;
 
        if (cnt == 0)
            printf("Case %d: No trees.\n", T);
        else if (cnt == 1)
            printf("Case %d: There is one tree.\n", T);
        else if (cnt >= 2)
            printf("Case %d: A forest of %d trees.\n", T, cnt);
    }
    return 0;
}