백준 4803 : Tree

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

그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성

트리의 기본 구조를 잘 구현하기~

 

#include <iostream>
#include <vector>
#include <cstring> // memset 사용
using namespace std;

int N, M, ans;               // 정점 수, 간선 수, 트리 개수
bool visited[501];           // 방문 여부 : 정점최대수500이나 벡터를 1부터 시작하므로 501
vector<int> v[501];          // 그래프 인접 리스트

bool DFS(int cur, int parent)
{
    visited[cur] = true;
    for (auto node : v[cur])// node는 현재 노드 cur에 연결된 각 인접 노드를 하나씩 담음
    {
        //연결된 노드들은 둘중하나 1)parent노드 2)!visited 자식노드
        if (!visited[node])//그 자식노드가 NOT visited면(즉 parent노드가 아니면)
        {
            if (DFS(node, cur)) //cur=parent이면
            {
                return true;//싸이클 존재
            }
        }
        else if (node != parent)//자식노드가 visited=true이고 부모노드도 아니면
        {
            return true;//쌍방향 간선이 나가서 싸이클 존재
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int testCase = 0;
    while (true)//N, M==0 종료조건 만날때까지 계속 진행
    {
        ans = 0; // 트리 개수 초기화
        cin >> N >> M;
        if (N == 0 && M == 0) break; // 종료 조건

        // 그래프 초기화
        for (int i = 1; i <= N; i++) 
        {
            v[i].clear();//인접 리스트(adjacent list)
        }
        memset(visited, false, sizeof(visited)); 
        // 방문 배열 flase로 초기화

        // 그래프 입력
        for (int i = 0; i < M; i++) 
        {
            int start, end;
            cin >> start >> end;
            v[start].push_back(end);//start → end 방향의 간선을 추가
            v[end].push_back(start);//end → start 방향의 간선도 추가
        }

        // 연결 요소 탐색 및 트리 확인
        for (int i = 1; i <= N; i++) 
        {
            if (!visited[i]) // 새로운 연결 요소
            { 
                if (!DFS(i, -1)) // 트리인지 재귀로 확인
                { 
                    ans++; // 트리 개수 증가
                }
            }
        }

        // print!~~~
        cout << "Case " << ++testCase << ": ";
        if (ans == 0) 
        {
            cout << "No trees.\n";
        }
        else if (ans == 1) 
        {
            cout << "There is one tree.\n";
        }
        else 
        {
            cout << "A forest of " << ans << " trees.\n";
        }
    }

    return 0;
}