[백준] 4803번 : 트리 (C++)

10984번: 내 학점을 구해줘

---

문제)

그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다.

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

 

 

 

입력 :

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n ≤ 500과 m ≤ n(n-1)/2을 만족하는 정점의 개수 n과 간선의 개수 m이 주어진다. 다음 m개의 줄에는 간선을 나타내는 두 개의 정수가 주어진다. 같은 간선은 여러 번 주어지지 않는다. 정점은 1번부터 n번까지 번호가 매겨져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다.

 

 

 

출력 :

입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다.

 

 

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
 
using namespace std;
 
int n, m;
bool flag;
 
void dfs(int cur, int prev, vector<vector<int>>& tree, vector<int>& visited)
{
    // 현재 노드 방문처리
    visited[cur] = 1;
 
    for (auto nxt : tree[cur])
    {
        if (nxt == prev) continue;
        // 이미 방문했던 곳을 또 가려고 한다면
        // 싸이클이 있는 것이므로 flag를 0으로 만들어준다
        if (visited[nxt])
        {    // 트리를 만들 수 없음
            flag = false;
            continue;
        }
        // 다음 노드 탐색
        dfs(nxt, cur, tree, visited);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int idx = 1;
    while (idx)
    {
        cin >> n >> m;
        if (n == 0 && m == 0) break;
        
        vector<vector<int>> tree(n + 1);
        vector<int> visited(n + 1, 0);
 
        int a, b;
        for (int i = 0; i < m; i++)
        {
            cin >> a >> b;
            tree[a].push_back(b);
            tree[b].push_back(a);
        }
 
        int cnt = 0;
        for (int i = 1; i < n + 1; i++)
        {
            if (visited[i]) continue;
            cnt++;
            flag = 1;
            dfs(i, -1, tree, visited);
            // 사이클이 있는 그래프라면 cnt--
            if (!flag) cnt--;
        }
 
        // cnt, 즉 트리의 갯수에 따라 출력해준다.
        cout << "Case " << idx << ": ";
        if (cnt == 0)
        {
            cout << "No trees.\n";
        }
        else if (cnt == 1)
        {
            cout << "There is one tree.\n";
        }
        else
        {
            cout << "A forest of " << cnt << " trees.\n";
        }
        idx++;
    }
 
    return 0;
}
 

---

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

4803번: 트리