백준 4803 c++ "트리" -PlusUltraCode-

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

[필자 사고]

트리 문제다. 사이클이 없는 트리의 갯수를 어떻게 판별해야 될까 .

공식이다. 정점 -1 == 간선의 수

 

그렇다면 dfs탐색을 통해 정점 수와 간선의 수를 파악해야 한다.

매번 탐색을 하게 되면 graph[node].size() 를 통해 간선의 수를 누적해서 더하고 방문할때마다 정점의 수 한개를 증가시킨다.

 

그리고 점검 타임이 중요하다.

간선은 양방향으로 연결되었기 때문에 

반드시 간선수/2 를 해야 된다. 

 

아래는 자세한 코드 해설이다.

[코드 해설]

dfs(int node)

• 매개변수로 현재 탐색할 정점 번호를 받는다.
• 현재 정점을 방문 처리한다 (visited[node] = true).
• 현재 정점에서 나가는 간선 수를 e에 더한다.
  이렇게 하면 연결 요소 전체의 간선 수를 셀 수 있다. 단, 무방향 그래프라서 간선이 두 번씩 세어지므로 나중에 e /= 2를 해준다.
• 인접한 정점(next)들을 순회하면서, 방문하지 않은 정점이면 정점 수(v)를 하나 늘리고 재귀적으로 dfs(next)를 호출한다.
• 결과적으로 하나의 연결 요소에서 정점 수(v)와 간선 수(e)를 모두 구할 수 있다.

---

main()

1. 빠른 입출력을 설정한다.
2. 테스트 케이스 번호를 caseNum = 1로 시작한다.
3. 무한 루프를 돌며 입력을 받는다.
   • n과 m이 모두 0이면 종료한다.
4. 초기화 단계:
   • 그래프 인접 리스트 graph[i]를 비운다.
   • visited[i] 배열을 모두 false로 초기화한다.
5. 간선 입력:
   • m개의 간선을 읽어서 양방향 그래프를 만든다 (graph[a].push_back(b), graph[b].push_back(a)).
6. 트리 개수 세기:
   • 모든 정점에 대해 방문하지 않은 정점이면 새로운 연결 요소를 발견한 것이므로
     • e = 0, v = 1로 초기화
     • dfs(i) 실행
     • 간선 수 e는 2로 나눠서 실제 간선 개수를 구한다.
     • 트리 판정: 간선 수가 정점 수 - 1과 같으면 해당 연결 요소는 트리이므로 treeCount++ 한다.
7. 출력 단계:
   • 트리 개수가 0 → "No trees."
   • 트리 개수가 1 → "There is one tree."
   • 트리 개수가 2 이상 → "A forest of X trees."
   • 출력할 때는 "Case N: ..." 형식을 지킨다.

---

전체 동작 원리

• main()에서 입력을 받아 그래프를 구성하고,
• 각 연결 요소마다 dfs()로 탐색하면서 정점 수와 간선 수를 센다.
• dfs()의 결과로 얻은 (v, e)를 이용해 e == v-1 조건을 만족하면 트리라고 판정한다.
• 최종적으로 트리의 개수를 세어 출력 형식에 맞게 출력한다.

[소스 코드]

#include <bits/stdc++.h>
using namespace std;

vector<int> graph[501];
bool visited[501];
int n, m;
int v = 1;
int e = 0;

void dfs(int node) {
    visited[node] = true;
    e += graph[node].size();
    for (int next : graph[node]) {
        if (!visited[next]) {
            v++;
            dfs(next);
        }
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int caseNum = 1;
    while (1) {
        cin >> n >> m;
        if (n == 0 && m == 0) break;

        // 초기화
        for (int i = 1; i <= n; i++) {
            graph[i].clear();
            visited[i] = false;
        }

        // 간선 입력
        for (int i = 0; i < m; i++) {
            int a, b; cin >> a >> b;
            graph[a].push_back(b);
            graph[b].push_back(a);
        }

        int treeCount = 0;
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                e = 0;
                v = 1;
                dfs(i);
                e /= 2; // 양방향 간선이므로 절반
                if (e == v - 1) treeCount++;
            }
        }

        cout << "Case " << caseNum++ << ": ";
        if (treeCount == 0) cout << "No trees.\n";
        else if (treeCount == 1) cout << "There is one tree.\n";
        else cout << "A forest of " << treeCount << " trees.\n";
    }
}